Aca te dejo un codigo que uso yo para paginar resultados.
Espero te sirva
Saludos
Código PHP:
//Limito la busqueda
$TAMANO_PAGINA = 10;
//Examino la página a mostrar y el inicio del registro a mostrar
$pagina = $_GET["pagina"];
if (!$pagina) {
$inicio = 0;
$pagina=1;
}
else {
$inicio = ($pagina - 1) * $TAMANO_PAGINA;
}
//Número total de campos que hay en la tabla con esa búsqueda
$ssql="";
///////////////////////////////////////////////
// //
// $ssql creamos la sentencia SQL //
// //
///////////////////////////////////////////////
$rs = mysql_query($ssql,$conn);
$num_total_registros = mysql_num_rows($rs);
//Calculo el total de páginas
$total_paginas = ceil($num_total_registros / $TAMANO_PAGINA);
//Construyo la sentencia SQL
$ssql = $ssql . " limit " . $inicio . "," . $TAMANO_PAGINA;
//Mostramos el resultado de la consulta
$rs = mysql_query($ssql);
while ($fila = mysql_fetch_object($rs)){
///////////////////////////////////////////////
// //
// Codigo para mostrar los resultados //
// //
///////////////////////////////////////////////
}
//Cerramos el conjunto de resultados y la conexión con la base de datos
mysql_free_result($rs);
mysql_close($conn);
//Muestro los distintos índices de las páginas, si es que hay varias páginas
if ($total_paginas > 1){
for ($i=1;$i<=$total_paginas;$i++){
if ($pagina == $i)
//si muestro el índice de la página actual, no coloco enlace
echo $pagina . " ";
else
//si el índice no corresponde con la página mostrada actualmente, coloco el enlace para ir a esa página
echo "<a href='index.php?pagina=" . $i . "&criterio=" . $txt_criterio . "'>" . $i . "</a> ";
}
}
Paginando el foro... 
