sayfalama örnegi ile yapabilirsin yapabilirsin
httaccess ile

RewriteEngine on
RewriteRule ^sitemap([0-9]+).xml$ sitemap.php?sayfa=$1

yaparsin sitemap.php ye kacinci map oldugunu gönderirsin.
sitemap.php de

$sayfa = $_GET['sayfa']; //kacinci map
$kactane = "5000"; //1 sayfaya cekilecek veri sayisi
$basla=($sayfa*$kactane)-$kactane; //verileri cekmeye nerden baslicaz sayfa sayisina göre
$sql = mysql_query("SELECT * FROM tablo LIMIT $basla,$kactane");
//daha sonra while işlemleri vs.

sonra
www.site.com/sitemap1.xml de ilk 5000 veri
www.site.com/sitemap2.xml de 2. 5000 veri
sitemap3.xml 3. 5000 veri gibi ilerler
bu bir örnek sadece geliştirebilirsin.