Зависимость скорости работы сервера от кол-ва файлов в папке?

Зависит от файловой системы. Для ext3/ext4 большое количество файлов не проблема.
Разделять нужно обязательно, т.к. будет удобней бекапить, обслуживать и разрабатывать.

Файловая система загружается от общего количества файлов на диске(не значительно) и частоты доступа к ним, количество файлов в папке ей по барабану.

Обязательно разделите. С ростом кол-ва файлов в одном каталоге вы и сами заметите медленный доступ к конкретному файлу по его полному пути, создайте пару уровней подкатегорий, чтоб не столкнуться с этой проблемой.
А на счёт панели управления хостера, тут немного другая ситуация. Панель сканирует содержимое вашей папки, учитывая количество файлов на это уходит какое-то время.

Надо делить, на миллионе когда будет опрашиваться папка, будет виден лаг.

Если я не ошибаюсь — в nix системах — всё есть файлы: папки, порты, устройства и тд. Поэтому ей пофиг. Файлы сохраняются на диске, не зависимо от папок.
Но я бы рекомендовал разделять по папкам. Представьте, что вы будете работать(посмотреть, удалить и т.д.) со списком файлов в 50k+, например.

Мы в проекте с ОЧЕНЬ большим кол-вом файлов зачем-то делили на папки вида вместо имени abcdefgh => a/b/c/abcdefgh. CTO наш сказал что так быстрее работает. Хотя я не проверял на практике.

То что проверял, то зайти в папку тем же MC с 10К файлов — не так просто…

я у себя делю по дате.
/images/2010/1/
/images/2011/10/
и т.п. боюсь считать сколько у меня там файлов, но возможночти терабайтного винта по inode я уже исчерпал на 50%