I think the easiest way to get two different language menus in the site would be to craft both of them, then use some php code to show only the correct one based on the selected language.
For example, if you have both menu include files on the page and have a session variable that is set for the language you could make one or the other show like this:
php:
if(isset($_SESSION['<your language var>']) && $_SESSION['<your language var>'] == "English"){
// the include for the English menu here
} else {
//the include for the French menu here
}
This is just an example of how an if statement might look for this, you would need to have your session variable for the language set, and have both English and French menus created already.
