How can I filter by taxonomy on a custom post type’s page?

wp_list_categories uses get_term_link to retrive the terms link.

This function have a filter that you can use to change what is returned.
A problem is that you have to pass the current post type to the function that hooks into the filter, but a global variable should works for the scope.

Of course you have to remove filter after all wp_list_categories calls, for not interfere with nex class of get_term_link.

So, in your functions.php put:

function convert_term_link_to_post_type( $termlink, $term, $taxonomy ) {
  global $the_current_type;
  if ( empty($the_current_type) ) return $termlink;
  $link = get_post_type_archive_link( $the_current_type );
  if ( $taxonomy == 'category') $taxonomy = "category_name";
  if ( $link ) return add_query_arg( array($taxonomy => $term->slug), $link );
  return $termlink;
}

Then change the code you posted like so:

$type = get_post_type();
$customPostTaxonomies = get_object_taxonomies($type);
if( count($customPostTaxonomies) > 0) {
  echo '<h3>Browse By:</h3>';
  // set the global variable
  global $the_current_type;
  $the_current_type = $type;
  // add the filter that convert the term link
  add_filter('term_link', 'convert_term_link_to_post_type', 20, 3);
  foreach($customPostTaxonomies as $tax) {
    $woah = get_taxonomy($tax);
    $args = array(
      'orderby' => 'name',
      'show_count' => 0,
      'pad_counts' => 0,
      'hierarchical' => 1,
      'taxonomy' => $tax,
      'title_li' => ''
    );
    echo '<ul>';
    echo '<h4>' . $woah->labels->name . '</h4>';
    echo wp_list_categories( $args );
    echo '</ul>';
  }
  // unset the global variable
  unset($the_current_type);
  // remove the filter to not alter any other 'get_term_link' calls
  remove_filter('term_link', 'convert_term_link_to_post_type', 20, 3);
}