Custom Taxonomy’s Label to change the text appearing in Appearance > Menu

I’m assuming that you don’t want to set different labels for these taxonomies in the first place – you didn’t specifically mention that you can’t, but I’m assuming the thought occurred to you.

Just in case it didn’t, from your code:

register_taxonomy("product_cat", "product", array(
  "labels" => array(
    "name" => "Categories",

Changing "Categories" to "Product Categories" will indeed change the menu label, as well as changing the label in every other relevant place across WordPress.

Now, chances are you knew that but you want it just to be different in the menu section. To do that, you can use the nav_menu_meta_box_object filter. The following should do the job for you, tested on WordPress 4.5.3:

add_action( 'nav_menu_meta_box_object', 'wpse216757_menu_metaboxes' );

function wpse216757_menu_metaboxes ( $tax ){
  if ( $tax->name === 'product_cat' ) {
    $tax->labels->name = "Product Categories";
  }
  return $tax;
}

What this does is takes the taxonomy object and returns a different name for it, only when dealing with the meta boxes on the menu page.