I think you should have a pagination resource that understands a resource and returns a paginated URL.

it would accept parameters. I think having a template requires the client to understand a format other than hypertext.