Turns out that there is just a small change to the way the pagination links need to be written out.
page/ needs to be prefixed to %#%
Corrected example below.
Hope this helps someone with the same issue in the future.
<?php // Pagination
echo paginate_links( array(
'base' => get_permalink() . 'page/%#%' . '/#gallery',
'format' => '?page=%#%',
'current' => $page,
'total' => $pages
) );
?>