One way round this (it doesn't change the sort order though) is to hard code a value in for number of links per page in link_listing.php in includes/modules.
It is written to take the value set up in admin for search results. If you set that value to 10 then you get 10 links per page, 10 products per page, etc. Hardcode link_listing.php to a higher value and you get more links but still get the defualt products per page.
If I was a link partner I'd want to always be on the first page as there is no incentive for a customer to want to click to extra pages.