Pagination is only possible with page templates like Portfolio 3 Column and not the sorted ones. If you change the template to Portfolio 3 Column or related ones, you can see that pagination works. You can enable Ajax on Portfolio pages too so that the items do a lazy load when the user scrolls down.
The reason why pagination is not possible with sorted templates – we need to know beforehand the items belonging to a category and if one or more items are in a different page, the user is being provided wrong information.