I'm assuming you already have the i18n Menu Translation sub-module is enabled (it is one of the Internationalization sub-modules).
Edit the menu to be translated, by navigating to admin/structure/menu/manage/main-menu/edit (for the "main menu"). From there you can select the translation mode you want, e.g. Translate and Localize (from your question it seems you also did that already).
With what's above you should be in pretty good shape to complete the finishing touch: when editing a menu link, there should be a new link Translate to actually translate the menu entry. After you entered a translation for the "original" (eg English) menu item in another language (eg Spanish), Drupal will ensure that whenever you switch to another language, the corresponding menu item will be switched also (to the matching language).
Should you have some other menu item in your original menu in that "other" language, you can safely delete that menu item. After you delete such item, that'll be 1 menu item less that is shown "in both languages" (as in your question). Repeat the above (= translate menu item and delete original duplicate item) for each of your duplicate (in both languages) menu items.
Refer to the Multilingual Guide for (way) more details.
Miltilingual sites are really fun in D7 (way better then it was in D6, and D8 promises to become more easy to configure). Typical variations (with similar solutions) of this "menu" topic are:
- translations of blocks, which requires the Block Languages (i18n_block) submodule to be enabled.
- translations of taxonomies, which requires the Taxonomy Translation (i18n_taxonomy) submodule to be enabled.