Hierarchical Select Question
You have a separate submodule for using Hierarchical Select with menus, the same as for taxonomy terms.

So, for taxonomy terms you have Hierarchical Select Content Taxonomy submodule (hs_taxonomy), and for menus you have Hierarchical Select Menu (hs_menu) submodule, which you should use in your case.

Click on 'Show config' links on the demo page you have mentioned to see the details.