I have made a custom menu handler for the back end, sorting the via a drag drop based on CMS Page Order.
The problem now is that it seems that it's not possible to sort wp_nav_menu in any other way than the default one, can that be really be true?
The nav_menu_items are already sorted by menu_order.
When you go into the Appearance -> Menus and arrange the order menu the menu_order of each menu item gets updated.
To change the orderby parameter in the query that displays the menu you can use pre_get_posts to alter it. Example:
ID and menu_order are your only real options for sorting using the default post table. There is no title and the post_name is the same as the ID.
You could add additional parameters to the pre_get_posts filter using the meta data stored with each nav_menu_item.
Nav Menu metadata: