You will need to convert the relative links to absolute links. You can do this in the wp_nav_menu_objects filter, which gets all menu items. Just edit the url property of each item.
Another option would be to extend the default Walker_Nav_Menu with one that overrides start_el(), so you can modify the passed $item there before you pass it to the parent start_el().
These are relative links you added yourself? If you add a link to a WordPress Page or Post via the menu editor it should be absolute by default.