XFS for now, and I like it.
100,000 files in the dir:
$ time find 000001_to_100000/ -name "pg_88298276500-??.pdf" -print
000001_to_100000/pg_88298276500-01.pdf
000001_to_100000/pg_88298276500-02.pdf
000001_to_100000/pg_88298276500-03.pdf
000001_to_100000/pg_88298276500-04.pdf
000001_to_100000/pg_88298276500-05.pdf
000001_to_100000/pg_88298276500-06.pdf
000001_to_100000/pg_88298276500-07.pdf
000001_to_100000/pg_88298276500-08.pdf
real 0m0.191s
user 0m0.110s
sys 0m0.080s
330,000 files (links to other dirs)
$ time find links/ -name "pg_88298276500-??.pdf" -print
links/pg_88298276500-01.pdf
links/pg_88298276500-02.pdf
links/pg_88298276500-03.pdf
links/pg_88298276500-04.pdf
links/pg_88298276500-05.pdf
links/pg_88298276500-06.pdf
links/pg_88298276500-07.pdf
links/pg_88298276500-08.pdf
real 0m0.600s
user 0m0.360s
sys 0m0.240s
If it goes to 5 seconds to whip through 2.2 million files, it'll for work me.