Un minimum de CSS pour habiller les liens :
<code css>
ul.pagination {
    text-align: center;
}

ul.pagination li {
    display: inline;
    margin: 10px 5px;
    padding: 5px;
    text-align: center;
}

ul.pagination li.page-courante {
    font-weight: bold;
}
</code>
Le fichier XML de test :
<code xml><root>
    <a id="1" />
    <b id="2" />
    <c id="3" />
    <d id="4" />
    <e id="5" />
    <f id="6" />
    <g id="7" />
    <h id="8" />
    <i id="9" />
    <j id="10" />
    <k id="11" />
    <l id="12" />
    <m id="13" />
    <n id="14" />
    <o id="15" />
    <p id="16" />
    <q id="17" />
    <r id="18" />
    <s id="19" />
    <t id="20" />
    <u id="21" />
    <v id="22" />
    <w id="23" />
    <x id="24" />
    <y id="25" />
    <z id="26" />
</root></code>
Le code PHP/DOM :
<code php><?php
// Encodage du script : UTF-8

// Nombre d'éléments à afficher sur une page
define('NB_PAR_PAGE', 2);
// Nom du fichier à traiter
define('FICHIER_XML', 'pagination.xml');
// Expression XPath de base (doit être encodée en UTF-8)
define('XPATH_EXPR', '/root/*[@id > 9]');

$page = isset($_GET['page']) ? intval($_GET['page']) : 1;
$dom = new DomDocument;
$dom->preserveWhiteSpace = FALSE;
$dom->load(FICHIER_XML);
$xpath = new DomXPath($dom);

$count = $xpath->evaluate('count('  . XPATH_EXPR . ')');
$debut_pos = ($page - 1) * NB_PAR_PAGE + 1;
$fin_pos = $page * NB_PAR_PAGE + 1;
$derniere_page = ceil($count / NB_PAR_PAGE);

/*if ($page < 1 || $page > $derniere_page) {
    die('Hors limite');
}*/

if ($count > 0) {
    $noeuds = $xpath->query(XPATH_EXPR . "[position()>=$debut_pos and position()<$fin_pos]");
    foreach ($noeuds as $n) {
        // afficher $n
        echo $n->tagName, '<br />'; // pour test
    }
    // Affichage de la barre de navigation
    if ($count > NB_PAR_PAGE) {
        echo '<ul class="pagination">';
        if ($page > 1) {
            echo '<li><a href="' . basename(__FILE__) . '?page=' . ($page - 1) . '">Page précédente</a></li>';
        }
        for ($i = 1; $i <= $derniere_page; $i++) {
            if ($i == $page) {
                echo '<li class="page-courante">' . $i . '</li>';
            } else {
                echo '<li><a href="' . basename(__FILE__) . '?page=' . $i . '">' . $i . '</a></li>';
            }
        }
        if ($page < $derniere_page) {
            echo '<li><a href="' . basename(__FILE__) . '?page=' . ($page + 1) . '">Page suivante</a></li>';
        }
        echo '</ul>';
    }
}</code>

On pourrait parfaitement utiliser SimpleXML mais il est plus gourmand étant donné qu'il n'est pas prévu pour évaluer des expressions XPath retournant autre chose que des noeuds :
<code php><?php
// Encodage du script : UTF-8

// Nombre d'éléments à afficher sur une page
define('NB_PAR_PAGE', 2);
// Nom du fichier à traiter
define('FICHIER_XML', 'pagination.xml');
// Expression XPath de base (doit être encodée en UTF-8)
define('XPATH_EXPR', '/root/*[@id > 9]');

$page = isset($_GET['page']) ? intval($_GET['page']) : 1;
$sxml = simplexml_load_file(FICHIER_XML);

$count = count($sxml->xpath(XPATH_EXPR));
$debut_pos = ($page - 1) * NB_PAR_PAGE + 1;
$fin_pos = $page * NB_PAR_PAGE + 1;
$derniere_page = ceil($count / NB_PAR_PAGE);

/*if ($page < 1 || $page > $derniere_page) {
    die('Hors limite');
}*/

if ($count > 0) {
    $noeuds = $sxml->xpath(XPATH_EXPR . "[position()>=$debut_pos and position()<$fin_pos]");
    foreach ($noeuds as $n) {
        // afficher $n
        echo $n->getName(), '<br />';
    }
    // Affichage de la barre de navigation
    if ($count > NB_PAR_PAGE) {
        echo '<ul class="pagination">';
        if ($page > 1) {
            echo '<li><a href="' . basename(__FILE__) . '?page=' . ($page - 1) . '">Page précédente</a></li>';
        }
        for ($i = 1; $i <= $derniere_page; $i++) {
            if ($i == $page) {
                echo '<li class="page-courante">' . $i . '</li>';
            } else {
                echo '<li><a href="' . basename(__FILE__) . '?page=' . $i . '">' . $i . '</a></li>';
            }
        }
        if ($page < $derniere_page) {
            echo '<li><a href="' . basename(__FILE__) . '?page=' . ($page + 1) . '">Page suivante</a></li>';
        }
        echo '</ul>';
    }
}</code>