How can you control the pagination URL and change this:
http://example.com/blog/P#
to this:
http://example.com/blog/page-#
? Any help appreciated.
There is nothing built into the EE core that would allow you to do this.
You have a few options though. The easiest would be to use something like Better Pagination which will allow you to setup different Pagination URLS.
The other option is to build the url you want and use some template logic to grab the correct URL.