Hola,
Revisa
www.php.net/dir . Con esas funciones puedes recorrer directorios. Simplemente haz que el subdirectorio se llame como el valor del parametro, abres ese directorio, y metes los nombres de los ficheros en un array (mayor facilidad de manejo).
Para la paginacion, pues pasas tambien la "pagina" de imagenes que quieres mostrar. Luego calculas la posicion en el array de la primera imagen en esa pagina y con un bucle muestras desde ese indice hasta ese indice+imagenes por pagina o el final del array, lo que ocurra antes.
Saludos.
PD: Seguro que hay por ahi scripts ya hechos, pero esta seria la descripcion de lo que hacen.