Untested, but this should at least be on the right track:

$posts_per_page = 50;

$page = ( get_query_var( 'paged' ) ) ? get_query_var( 'paged' ) : 1;
$offset = ( $page - 1 );

$args = array(
    'child_of' => 504,
    'order_by' => 'name',
);
$categories = get_categories( $args );

for( $i = $offset * $posts_per_page; $i < ( $offset + 1 ) * $posts_per_page; $i++ ) {
    $category = $categories[$i];
    echo '<a href="' . get_category_link( $category->term_id ) . '" title="' . sprintf( __( "View all posts in %s" ), $category->name ) . '" ' . '> '. get_the_term_thumbnail ( $category->term_id, category, $size="medium", $attr="") . ' </a><a href="' . get_category_link( $category->term_id ) . '" title="' . sprintf( __( "View all posts in %s" ), $category->name ) . '" ' . '>' . $category->name.'</a>';
}
unset( $category );

secondary pagination method

if( strpos( $_SERVER['REQUEST_URI'], '/page/' ) !== false ) {
    $uri = explode( "https://wordpress.stackexchange.com/", $_SERVER['REQUEST_URI'] );
    foreach ( $uri as $k => $v ) {
        if ( $value == "" )
            unset( $uri[$k] );
    }
    $offset = ( array_pop($uri) * $posts_per_page ) - $posts_per_page;
}

That will check the URL for /page/, if it contains /page/ it will strip all the empty values out and set the offset to the final value of the array. It’s not the most elegant solution, but it works and its good on processing power