Из личного опыта, sitemap это не тот файл, который постоянно открывают, соотвественно можно пожертвовать производительностью и генерировать его в режиме онлайн.
Второе важное наблюдение sitemap не обязан быть по адресу sitemap.xml , в моих проектах он доступен по адресу site.ru/sitemap и это вполне хорошо работает.
По поводу предела юрл, во первых страницы которых нету в сайт мапе тоже индексируются, при хорошей доступности с главной страницы они быстро попадут в индекс.
Потом можно делать несколько сайтмап файлов