as far as I know pagination comes from joomla itself, to change its markup you need to override it in joomla template, see protostart html folder for example.
Actually since joomla 3 and something, there is also a layout file for pagination so you can override that directly, see layouts/joomla/pagination - to override it you need to copy folder structure to the template html folder.