Interesting.... that's a difficult system to work with. Are you required to send the number of results and page number through that URL for the feed? If so, the you're going to have to define how many results per page (seems like you want 5) and then define which page you're on using a $_GET variable. I'm not 100% sure it's possible without getting all the results in the RSS feed......
But if you were to get all the results in the RSS feed, you could simply just take the total number of results given, [man]ceil/man the result of $total_rows/$rows_per_page (which you said was 5). Then you've got your total number of pages. Then you just need to construct the links, define what "id" you're starting from (0, 5, 10, 15, 20, etc.) and count from there to the fourth one. So the first page would list IDs: 0, 1, 2, 3, 4. The second would be: 5, 6, 7, 8, 9. And so on.
The reason it's so difficult to just change your coding right now is because you're not privy to the information you need (total number of rows for the feed), so you can't properly calculate the number of pages there really are.
Sorry to be the bearer of bad news.