Pagination not working with custom category template

As this is your main loop of your template, you should not be making a new loop, but modify the existing loop with pre_get_posts. This way you can be sure that all extra query parameters will be taken into account.

An example of how you would do this:

add_action( 'pre_get_posts', 'wpse5477_pre_get_posts' );
function wpse5477_pre_get_posts( $query )
{
    if ( ! $query->is_main_query() || $query->is_admin() )
        return false; 

    if ( $query->is_category() ) {
        $query->set( 'post_type', 'video' );
        $query->set( 'posts_per_page', 6 );
    }
    return $query;
}

This code will go in your functions.php.

First we check if this is the main loop and not your admin area. pre_get_posts can affect admin.

Then, if this is a category, we modify the $query.

And then return the $query.

For more information check here: https://codex.wordpress.org/Plugin_API/Action_Reference/pre_get_posts