How to paginate with an query var appended to permalink?

I ended up going with the regex. In my case that looks like:

 add_rewrite_rule('^messages/messages-app-view/page/?([0-9]{1,})/?$', 
'index.php?pagename=messages&messages-app-view&paged=$matches[1]', 'top');

tech