As has already been mentioned, this is basicly a hardware problem. Disk access is always slow, and most file systems aren’t really designed to handle directories with that many files.
If you for some reason have to store all the files in the same directory, I think you’ll have to maintain your own cache. This could be done using a local database such as sqlite, HeidiSQL or HSQL. If you want extreme performance, use a java TreeSet and cache it in memory. This means at the very least that you’ll have to read the directory less often, and it could possibly be done in the background. You could reduce the need to refresh the list even further by using your systems native file update notification API (inotify on linux) to subscribe to changes to the directory.
This doesn’t seem to be possible for you, but I once solved a similiar problem by “hashing” the files into subdirectories. In my case, the challenge was to store a couple of millions images with numeric ids. I constructed the directory structure as follows:
images/[id - (id % 1000000)]/[id - (id % 1000)]/[id].jpg
This has worked well for us, and it’s the solution that I would recommend. You could do something similiar to alpha-numeric filenames by simply taking the first two letters of the filename, and then the next two letters. I’ve done this as well once, and it did the job as well.