<?php
for($t=1;$t<=10000;$t++) {
?>
<url>
<loc>www.example.com?history=<?php echo $t; ?></loc>
<lastmod>2005-08-03</lastmod>
<changefreq>monthly</changefreq>
<priority>0.5</priority>
</url>
<?php
}
?>
De este modo, escribes 1000 veces el mismo bloque de texto cambiando el número, pero si quieres también modificar los valores de fecha y donde dice monthly vas a necesitar sacarlos de alguna Base de Datos, o a lo peor, ponerlos en un array y después imprimirlos. No es complicado, solo sigue los ejemplos que ya se han puesto.