Teoretic se poate face ori de cate ori ti-ai updatat siteul. Asta este scopul unui sitemap, Google nu-l va considera spam.
Pana la urma depinde de tipul site-ului, nr de url-uri si de timpul tau liber.
Io de exemplu, la un site cu ~80K urls pun noul sitemap 1 data pe saptamana. Pe site se adauga cam 20 de url-uri noi/zi, deci la fiecare sitemap update am cam 100-200 de noi url-uri pt google.
Oricum, din ce am observat, google vine la mine pe site cam 1 data pe zi, indiferent daca am pus un nou sitemap sau nu, deci frecventa cu care updatezi sitemapul e mai mult cu scop informativ.