Eu quase nunca faço duas consultas.
Basta retornar uma linha a mais do que o necessário, exibir apenas 10 na página e, se houver mais do que o exibido, exibir um botão "Avançar".
SELECT x, y, z FROM `table` WHERE `some_condition` LIMIT 0, 11
// iterate through and display 10 rows.
// if there were 11 rows, display a "Next" button.
Sua consulta deve retornar na ordem do mais relevante primeiro. Provavelmente, a maioria das pessoas não vai se importar em ir para a página 236 de 412.
Quando você faz uma pesquisa no Google e seus resultados não estão na primeira página, você provavelmente vai para a página dois, não para a nove.
