I managed to get to about 30 seconds with 65,000 files on a local ext3 file system. The file names where all of the same length and with a ~100 character long identical prefix. I re-mounted the file system before the ls to eliminate caching.