Bueno, pues en los enlaces a las distintas paginas pasas la pagina a mostrar, de 1 a n. Luego calculas el primer elemento de esa pagina con:
ipp * (pagina-1)
Siendo ipp el numero de imagenes por pagina, y pagina la pagina a mostrar. Entodes haces el bucle:
Código PHP:
$inicio=$ipp * ($pagina-1)
for ($i=$inicio;$i<inicio+$ipp;$i++) {
// mostramos la imagen
echo $imagenes[$i];
}
Luego los links a las distintas paginas los generas como para las paginaciones de resultados de consolas, en base al numero total de elementos del array.
Suerte.
PD: scandir() solo existe en PHP 5.