paginate_links 404 error when I click on any page

I am trying to implement pagination using paginate_links on post. The links appear at the bottom of the page correctly, but when I try to click on any of the pages I get the 404 page.

The code:

$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
            $wp_query = new WP_Query(array('posts_per_page' => 10, 'paged' => $paged ));
            while($wp_query->have_posts()) : $wp_query->the_post();

I set the post count per page to 10 in WP admin. The post list uses the page-blog.php template.

The pagination code:

global $wp_query;

        $total_pages = $wp_query->max_num_pages;

        if ($total_pages > 1){

          $current_page = max(1, get_query_var('paged'));

          echo paginate_links(array(
              'base' => get_pagenum_link(1) . '%_%',
              'format' => '/page/%#%',
              'current' => $current_page,
              'total' => $total_pages,
              'prev_text' => 'Next',
              'next_text' => 'Previous'
            ));

        }

The permalinks are set to /%category%/%postname%/ but I also tried with just %postname%. None of them worked. Not even if I set it back to the default permalink structure.
The url for the template where the pagination should appear: mydomain.com/blog/ When I click on the second page it looks like this: mydomain.com/blog/page/2/ and the 404 page appears.

What’s wrong with the code?