Te paso una versión simplificada, sin html a ver si te sirve:
Código PHP:
<?
$total_registros = 100;
$pagina = 15;
$total_paginas = $total_registros/$pagina;
for($i=0;$i<$total_paginas;$i++){
if(($pagina*$i)>=$total_registros) break;
echo "<a href=\"".$_SERVER['PHP_SELF']."?pagina=$i\">Pagina $i</a><br/>";
}
echo "<h3>Total registros: $total_registros</h3>";
echo "<h3>Total páginas: ".floor($total_paginas)."</h3>";
if(isset($_GET['pagina'])){
echo "<h3>Mostrando página ".$_GET['pagina'].", registros desde el ".($pagina*$_GET['pagina']?$pagina*$_GET['pagina']:"1")." hasta el ".($pagina*($_GET['pagina']+1)<=$total_registros?$pagina*($_GET['pagina']+1):$total_registros)."</h3>";
}
?>
Un saludo