Implement i18n menu's programmatically
Ensure the i18n_menu module is enabled and the menu to which you're adding links is configured to "Translate and Localize" on the Menu edit page:

For example, the setting for the main menu would be found at the following url: 

/admin/structure/menu/manage/main-menu/edit


The configuration option looks like this: