Se non vuoi fare un altra query, potresti fare una cosa di questo tipo:
Fai la query che prende il totale dei record e quando fai il while per creare l'array dei record, gli dai un indice alle variabili.
$i=0;
while(...){
$i++;
$nome[$i] = $result['nome'];
}

Cosi' facendo hai i record numerati e al momento della stampa, ti crei 2 variabili in base ala pagina scelta e fai un ciclo cosi':

$recordIniziale = (..fai i calcoli per vedere da dove partire);
$limite = numero record per pagina
for($i=$recordIniziale;$i<=($recordIniziale+$limit e);$i++){
//e qui ti stampi i record
echo $nome['$i'];
}
PS di solito faccio come dice Piero per il totale cmq.