Use images in pagination links
You have to override theme_pager_link() as well. The last line calls the l() function and you have to force it to render html.

Another possibility is to use css to theme the links