Magento – Magento 2 product list page pagination not working

As you are having Sort By option that means you have <?php echo $this->getToolbarHtml() ?> in your list.phtml file.

Check in the catalog.xml whether you have called xml for pagination. The xml should be as below

<block type="catalog/product_list_toolbar" name="product_list_toolbar" template="catalog/product/list/toolbar.phtml">
     <block type="page/html_pager" name="product_list_toolbar_pager"/>
</block>

You need to override Magento/Catalog/view/frontend/templates/product/list.phtml using your custom module.

in that file magento display toolbar using below code

<?php echo $block->getToolbarHtml() ?>

do your stuff over there.