You're looking at making significant changes to the form builder
menu_overview_form (e.g. via
hook_form_alter()) or perhaps a complete replacement at the menu route admin/structure/menu/manage/%menu handler (e.g.
Looking at the form builder shows the scope of the problem, it is making DB query that you'll need to augment with relevant logic for combining with language column. In addition, there is helper function,
_menu_overview_tree_form() that builds out the form elements that is coupled with the
$tree structure that's coupled with the result of DB query.
Given that, it might be easier for you to replace the route handler with your own custom form than trying to hack around the existing form. You certainly don't want to start hacking menu.admin.inc as your question implies.