Multiple WP_Query With Custom Post Type & Pagination

Basically I have two post types set up, “Dog” and “Cat”. I have a page template with two WP_Query loops displaying the two latest posts from each post type in each loop. Below is how I’m registering the post types:

<?php
  function cat_post_type() { 
    register_post_type( 'cat',
      array('labels' => array(
        'name' => __('Cats', 'bonestheme'),
        'singular_name' => __('Cat', 'bonestheme'),
        'all_items' => __('All Cats', 'bonestheme'),
        'add_new' => __('Add New', 'bonestheme'),
        'add_new_item' => __('Add New Cat', 'bonestheme'),
        'edit' => __( 'Edit', 'bonestheme' ),
        'edit_item' => __('Edit Cats', 'bonestheme'),
        'new_item' => __('New Cat', 'bonestheme'),
        'view_item' => __('View Cat', 'bonestheme'),
        'search_items' => __('Search Cat', 'bonestheme'),
        'not_found' =>  __('Nothing found in the Database.', 'bonestheme'),
        'not_found_in_trash' => __('Nothing found in Trash', 'bonestheme'),
        'parent_item_colon' => ''
        ),
        'description' => __( 'This is the cat post type', 'bonestheme' ),
        'public' => true,
        'publicly_queryable' => true,
        'exclude_from_search' => false,
        'show_ui' => true,
        'query_var' => true,
        'menu_position' => 8,
        'rewrite'  => array( 'slug' => 'cat', 'with_front' => false ),
        'has_archive' => 'cats',
        'capability_type' => 'post',
        'hierarchical' => false,
        'supports' => array( 'title', 'editor', 'thumbnail' )
       )
    );
  } 
  add_action( 'init', 'cat_post_type' );

  function dog_post_type() { 
    register_post_type( 'dog',
      array('labels' => array(
        'name' => __('Dogs', 'bonestheme'),
        'singular_name' => __('Dog', 'bonestheme'),
        'all_items' => __('All Dogs', 'bonestheme'),
        'add_new' => __('Add New', 'bonestheme'),
        'add_new_item' => __('Add New Dog', 'bonestheme'),
        'edit' => __( 'Edit', 'bonestheme' ),
        'edit_item' => __('Edit Dogs', 'bonestheme'),
        'new_item' => __('New Dog', 'bonestheme'),
        'view_item' => __('View Dog', 'bonestheme'),
        'search_items' => __('Search Dog', 'bonestheme'),
        'not_found' =>  __('Nothing found in the Database.', 'bonestheme'),
        'not_found_in_trash' => __('Nothing found in Trash', 'bonestheme'),
        'parent_item_colon' => ''
        ),
        'description' => __( 'This is the dog post type', 'bonestheme' ),
        'public' => true,
        'publicly_queryable' => true,
        'exclude_from_search' => false,
        'show_ui' => true,
        'query_var' => true,
        'menu_position' => 8,
        'rewrite'  => array( 'slug' => 'dog', 'with_front' => false ),
        'has_archive' => 'dogs',
        'capability_type' => 'post',
        'hierarchical' => false,
        'supports' => array( 'title', 'editor', 'thumbnail' )
       )
    );
  } 
  add_action( 'init', 'dog_post_type' );
?>

And below is how I am displaying the post types:

<?php
  $cat_query = new WP_Query(
    array(
      'posts_per_page' => 2,
      'post_type' => 'cat'
    )
  );
  if($cat_query->have_posts()) :
?>

  <div>
    <?php
      while($cat_query->have_posts()) :
      $cat_query->the_post();
    ?>
      <div>
        <a href="<?php the_permalink(); ?>">
          <?php the_title(); ?>
        </a>
      </div>
    <?php
      endwhile;
      wp_reset_postdata();
    ?>
  </div>

<?php endif; ?>

<?php
  $dog_query = new WP_Query(
    array(
      'posts_per_page' => 2,
      'post_type' => 'dog'
    )
  );
  if($dog_query->have_posts()) :
?>

  <div>
    <?php
      while($dog_query->have_posts()) :
      $dog_query->the_post();
    ?>
      <div>
        <a href="<?php the_permalink(); ?>">
          <?php the_title(); ?>
        </a>
      </div>
    <?php
      endwhile;
      wp_reset_postdata();
    ?>
  </div>

<?php endif; ?>

I want them to be able to co-exist with their own pagination, much like here (watch the video) but that only seems to work with just normal WP posts, not custom post types. If anyone has any idea on how to achieve this, that would be amazing because this is driving me crazy!

EDIT

I’ve almost achieved it with the following code but it’s buggy, for example, if I go to page three on both paginations, then click page one on the cat post type pagination, it will go to the same URL it’s already on:

<?php
  $paged1 = isset( $_GET['paged1'] ) ? (int) $_GET['paged1'] : 1;
  $cat_query = new WP_Query(
    array(
      'posts_per_page' => 2,
      'post_type' => 'cat',
      'paged'  => $paged1
    )
  );
  if($cat_query->have_posts()) :
?>

  <div>
    <?php
      while($cat_query->have_posts()) :
      $cat_query->the_post();
    ?>
      <div>
        <a href="<?php the_permalink(); ?>">
          <?php the_title(); ?>
        </a>
      </div>
    <?php
      endwhile;
      echo paginate_links(
        array(
          'format'   => '?paged1=%#%',
          'current'  => $paged1,
          'total'    => $cat_query->max_num_pages,
          'add_args' => array( 'paged2' => $paged2 )
        )
      );
      wp_reset_postdata();
    ?>
  </div>

<?php endif; ?>

<?php
  $paged2 = isset( $_GET['paged2'] ) ? (int) $_GET['paged2'] : 1;
  $dog_query = new WP_Query(
    array(
      'posts_per_page' => 2,
      'post_type' => 'dog',
      'paged'  => $paged2
    )
  );
  if($dog_query->have_posts()) :
?>

  <div>
    <?php
      while($dog_query->have_posts()) :
      $dog_query->the_post();
    ?>
      <div>
        <a href="<?php the_permalink(); ?>">
          <?php the_title(); ?>
        </a>
      </div>
    <?php
      endwhile;
      echo paginate_links(
        array(
          'format'   => '?paged2=%#%',
          'current'  => $paged2,
          'total'    => $dog_query->max_num_pages,
          'add_args' => array( 'paged1' => $paged1 )
        )
      );
      wp_reset_postdata();
    ?>
  </div>

<?php endif; ?>