The same problem here. I have temporarily fixed it by the hacking of pagination.php but this is unsustainable.
Please note that the problem persists even if the frontend template is changed, so it is not about the incorrect overriding of pagination.php by the template implementation.
Problem is discussed also here:
forum.joomla.org/viewtopic.php?t=875002&p=3273016
I can confirm the observations made there. I.e. if JoomSEF is disabled and default Joomla SEF is enabled, the pagination works correctly. So I can provisionally conclude that it is rather the problem of JoomSEF and not Joomla.