Well, this would be easy to do with an RDBMS, and given the sheer number of files, this may be the best way to do it.

Read the directory in and put it into a table, in the method of your choice. In mySQL, an autoincrement field can create an "index" field for you, by which you can have a field that allows you to order and manage the files, separate from the filenames, which may or may not be sequential. Then, using the "limit" function, you can select and create links to the next "x" files, like so:

select id,filename from files where id=$startid order by id limit 10

It's then a simple thing to create a script that would allow you to page through these files. This would be very fast also, given the RDBMS backend, and you could have users choose how many to see per page.

If the files change frequently, you can set up a cron job that would regularly update the table at the interval of your choice.

There are advantages and disadvantages to this system, of course, but I've done something similar. The script I wrote manages a directory with about 1600 image files in it, and it works excellently.