I just wanted to add that the Low Replace plugin is very useful in rewriting pagination URLs for other purposes. For example, if you need to enable query strings in your EE site (perhaps because member confirmation emails contain links with query strings in), you end up with pagination links turning into things like this:
<a href="http://mydomain/segment1&per_page=P5">http://mydomain/segment1&per_page=P5</a>
Supposedly this behaviour can be overridden with the page_query_string parameter, but it seems there may be a bug with it, and the parameter is ignored. However, you can work around this bug by using Low Replace and changing the {pagination_links} tag to the following:
{exp:low_replace find="[\\/]*&per_page=(P[0-9]+)|/&per_page=" replace="/$1/|" regex="yes" multiple="yes"}{pagination_links}{/exp:low_replace}
(Note that the above gives you a trailing slash in the new URL: if you don’t want a trailing slash, omit the second slash in the replace text.)
You can also use Low Replace to localise the pagination link text and URLs.
Simon