Splitting up a submenu into columns, or putting existing menus in another menu as submenu item

You can use the Walker class to customize your menus however you like.

A simple example of using Walker to create a custom menu can be found on the official WordPress Codex, here:

http://codex.wordpress.org/Class_Reference/Walker#General_Menu_Example

To do what you want using Walker, you would probably want to ensure that your menu has X parent items (where X is the number of columns you want), and each of your menu items is organized under one of those.

You would then use the Walker::start_lvl() and Walker::end_lvl() to output the container HTML for each of your columns, and Walker::start_el() to output each individual item.