wp_nav_menu showing taxonomies in a submenu with two columns

Question

I have this wp_nav_menu:

<?php wp_nav_menu( array( 
   'theme_location' => 'mainnavleft',
   'container' => '',
   'items_wrap' => '%3$s',
   'fallback_cb' => 'false' 
)); ?>

which looks like this:

Is it possible to make the Custom post type submenu show a two column list with taxonomies and the taxonomy title like the image?

I could do something similar adding all taxonomy's items manually and styling them with css, but that way i can't have the tax title and it isn't the better aproach for sure.

The code i'd need to render for custom post type menu would be something like this:

<li><a href="#">CUSTOM POST TYPE</a>

    <div class="2columns">

        <div class="col_1">
            <h3>Taxonomy 1</h3>
            <ul>
                <li><a href="#">item1</a></li>
                <li><a href="#">item2</a></li>
                <li><a href="#">item3</a></li>
            </ul>   
        </div>

        <div class="col_1">          
            <h3>Taxonomy 2</h3>
            <ul>
                <li><a href="#">item1</a></li>
                <li><a href="#">item2</a></li>
                <li><a href="#">item3</a></li>
            </ul>                   
        </div>   

    </div>
</li>

or similar structure