Currently (with WP 3.5.1) we ain’t got any possibility (means: no hook or filter) to alter the output of the pagination. Everything inside the WP_Posts_List_Table class and its method pagination() and the WP_List_Table class method pagination is hard coded.
So your only chance would be to replace the $GLOBAL on the fly with a class that extends the core WP_Post_List_Table.