Отталкивайтесь от ограничений Гугла. 50 тысяч адресов.
Для удобства стоит в принципе поделить всю пачку на более осмысленные множества: категории, товары, статьи, служебное. Для Гугла - ещё и картинки, Яндекс такое не понимает.
В принципе стоит разобраться с тем, зачем поисковикам нужен sitemap.xml: это список URL, которые должны попасть в индекс поисковиков, и которые поисковый робот должен хоть иногда обходить с каким-то приоритетом.
В конце концов, возьмите сайты из топов и посмотрите, как всё реализовано. Всё давно известно и опробовано на практике.
