How can I change the output display of my pagination?

I could see that you are trying to achieve the following output:

<div class="pagination">
  <span>Page {current} of {total pages}</span>
  {links here}
</div>

And you attempted it like so:

'before_page_number' => '<div class="pagination"><span>Page '. // wrapped for clarity
  $paged .' of ' . $term->max_num_pages . '</span></div>'

But that will actually add the markup before each and every page number in the generated links. (And the $term->max_num_pages is also a null because in that context, $term doesn’t have a max_num_pages property.)

So here’s how you could achieve the expected output:

$big = 999999999; // need an unlikely integer
$cur_page = max( 1, $paged );
$num_pages = ceil( $number_of_terms / $per_page );
$links = paginate_links(
    array(
        'base'    => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
        'format'  => '/page/%#%',
        'current' => $cur_page,
        'total'   => $num_pages,
        'prev_text' => __(''),
        'next_text' => __('')
    )
);

// If there are links to paginate, display the pagination.
if ( $links ) {
    $before="<span>Page ". $cur_page .' of ' . $num_pages . '</span>';
    echo '<div class="pagination">' . $before . ' ' . $links . '</div>';
}

See the paginate_links() reference for more details on that function, such as the mid_size and end_size parameters that control the number of pages/links to be displayed.