Faits : A. B._ SA, dont la raison sociale était, jusqu'en 2001, C._, est une société anonyme de droit français active dans le domaine de l'électronique civile et militaire. La majorité de son capital-actions était détenue, jusqu'en 1998, par l'Etat français. B. Entre le mois de juin 1989 et le mois d'août 1991, des négociations sont intervenues entre l'Etat français et la République de Chine (Taïwan) au sujet de la vente à cette dernière de six navires de type fff, pour un marché total d'environ 2,5 milliards d'euros. Ces négociations s'inscrivaient dans un contexte diplomatique extrêmement sensible, la République populaire de Chine s'opposant à toute fourniture d'armements en faveur de la République de Chine (Taïwan). Afin que l'Etat français ne se voie pas reprocher une violation de la souveraineté territoriale de la République populaire de Chine, il fut convenu que le contrat relatif à la vente des six navires serait officiellement conclu au nom de B._ SA. C. A._, citoyen de la République de Chine (Taïwan), était à la tête de deux sociétés de consulting, dont D._ Ltd, enregistrées à Taïwan et actives dans le commerce et l'importation d'équipement et de communication et d'autres équipements électroniques à Taïwan. D. Le 26 septembre 1989, en vue de la négociation du contrat de vente des navires, B._ SA et D._ Ltd, dont A._ était l'actionnaire principal, ont passé un contrat soumis au droit français et à l'arbitrage ICC (International Chamber of Commerce) à Paris en cas de litige. D._ Ltd devait tenir sa cocontractante régulièrement informée de l'évolution de cette vente potentielle, en particulier du point de vue financier, technique et commercial. A la demande de B._ SA, elle devait participer aux négociations à venir et la soutenir à cette fin (art. 1). La rémunération de la société était fixée à 15 % du prix de vente total (2,5 milliards d'euros), soit quelque 375'000'000 EUR (art. 4), réputée irrévocablement acquise seulement lorsque les encaissements de B._ SA en vertu du contrat de vente seraient considérés irrévocables selon ce contrat (art. 5). Aucune clause n'interdisait la rémunération de tiers en vue de la conclusion de la vente. E. E.a. Les négociations ont abouti, le 31 août 1991, à la signature d'un contrat, G._, entre B._ SA, agissant en qualité de représentant de plusieurs partenaires, et la Marine de la République de Chine (Taïwan), représentée par H._. La République de Chine (Taïwan) se portait acquéreur de six navires d'observation et de surveillance pour un prix brut de 2'525'692'731 USD (taxes comprises). E.b. Selon l'art. 18 de ce contrat, intitulé " gratuité et commission ", B._ SA s'engageait à n'accorder aucun don, cadeau ou paiement personnel à des employés ou fonctionnaires (officiers) de la Marine de la République de Chine qui agissait pour le compte de l'Etat (18.1). Elle y garantissait en outre n'avoir pas employé ou commissionné de société ou de personne autre que ses propres employés pour faire aboutir ce contrat et n'avoir pas désigné d'agent, de représentant ou autre personne, qui aurait reçu ou devrait recevoir une commission, un pourcentage, une commission de courtage ou des honoraires en relation avec ce contrat (art. 18. 2). En cas de violation de ces dispositions, il était prévu que l'acheteur aurait le droit, soit d'annuler le contrat, soit de déduire du prix un montant égal à celui des commissions versées par la venderesse (art. 18.3). F. En exécution du contrat du 16 septembre 1989 passé avec A._, B._ SA a procédé, entre octobre 1991 et septembre 1998, en fonction de ses encaissements successifs sur le prix de vente des navires, à des virements de sommes totalisant plus de 520'000'000 USD sur des comptes ouverts en Suisse auprès de E._ SA, au nom de sociétés dont A._ était l'ayant droit économique. Entre 2000 et 2001, ces comptes ont été clôturés et les avoirs y relatifs transférés sur des comptes ouverts auprès de diverses autres établissements bancaires suisses au nom de membres de la famille de A._ ainsi que de sociétés offshore sises aux Iles Vierges Britanniques et aux Iles Caïmans. G. G.a. Le 22 août 2001, alors qu'il était apparu depuis plusieurs mois que des commissions illicites avaient été versées dans le cadre de la conclusion du contrat du 31 août 1991, la République de Chine (Taïwan) a engagé à l'encontre de B._ SA la procédure arbitrale convenue en cas de litige afin d'obtenir la restitution des sommes censées avoir été versées à A._ en violation de l'art. 18 (cf. supra, consid. E.b). G.b. Le litige, soumis au droit français en vertu d'une clause d'élection de droit, a abouti à la sentence arbitrale du 20 avril 2010, aujourd'hui exécutoire. Le tribunal arbitral a considéré que, en tant que A._ était intervenu à l'époque de la conclusion du contrat de vente des navires en qualité d'agent officiel de B._ SA, à Taïwan, l'art. 18.2 du contrat qui interdisait l'emploi d'intermédiaire pour l'obtention du marché avait été violé. Il a en outre retenu que B._ SA avait violé l'art. 18.1 en effectuant des paiements indirects, par le biais de A._, à l'officier de la marine taïwanaise en charge de l'acquisition des navires, lequel avait reçu au moins 17'588'141 USD. Outre les frais, B._ SA a ainsi été condamnée à payer à la République de Chine (Taïwan) 482'326'869 USD, 209'341'703 FF et 38'770'785 EUR, plus intérêts. S'y ajoutaient encore 80'000'000 FF en relation avec des sommes versées à un autre agent. G.c. Dans un communiqué du 9 juin 2011, le Ministère français de la défense a notamment pris acte du caractère définitif de cette sentence, relevant en substance qu'il appartenait au budget public de solder " les comptes d'un passé ambigu " qui avait pesé lourdement sur l'image de l'industrie d'exportation d'armement naval et que, désormais, toute " équivoque " était finie, la France ayant ratifié en 2000 une convention relative à la " lutte contre la corruption d'agents publics étrangers dans les transactions commerciales internationales ". G.d. En exécution de la sentence, B._ SA a versé, le 12 juillet 2011, une somme dont la contrevaleur s'élève à 773'749'000 CHF. L'essentiel de ce montant, soit 460'800'000 EUR environ, devait être supporté en dernière ligne par l'Etat français, qui garantissait la Direction des constructions navales, entreprise publique ayant oeuvré à hauteur de 73 % du contrat de vente, B._ SA n'assumant que 27 % des prestations. H. En 2000 et 2001, des procédures pénales ont été ouvertes en Suisse, à Taïwan et en France. H.a. En Suisse, la procédure portait sur les infractions de blanchiment d'argent et d'escroquerie. Il était reproché à A._ et à son fils d'avoir, en 2000 et 2001, notamment par de fausses déclarations sur l'origine des avoirs nouvellement placés auprès d'intermédiaires financiers en Suisse, entravé l'identification de la commission illicite versée par B._ SA sur le contrat des navires dont ils savaient ou ne pouvaient ignorer qu'elle s'inscrivait dans le cadre d'une corruption franco-taïwanaise. L'enquête a été suspendue le 17 décembre 2008. H.b. Les autorités de poursuite taïwanaises ont accusé A._ d'avoir obtenu et organisé la transmission d'informations classées secrètes concernant le marché des navires en corrompant des militaires de haut rang et d'avoir été le bénéficiaire, le gestionnaire et le redistributeur du produit de la corruption pour un montant de 520'000'000 USD sur les quelque 920'000'000 USD que B._ SA lui avait versés sur des comptes en Suisse dont il était le titulaire ou l'ayant droit dans le cadre de plusieurs achats d'armement. H.c. En France, l'enquête pénale, qui avait pour objet des infractions de tentative d'escroquerie, abus de biens sociaux et recel dans le cadre de la conclusion ou de l'exécution de contrats de commission en relation avec la vente des navires, a été close par ordonnance de non-lieu du 1 er octobre 2008. L'instruction ne pouvait en effet porter sur les faits relevant de la corruption d'agents publics étrangers, ceux-ci n'étant pas punissables en France avant la signature de la convention ad hoc en 2000 (cf. supra, consid. G.c). I. I.a. Le 18 octobre 2011, B._ SA a requis le séquestre, à hauteur de 773'749'000 CHF., plus intérêts à 5 % dès le 29 avril 2010, des avoirs déposés sur divers comptes ouverts auprès d'établissements bancaires genevois, zurichois et bâlois au nom de membres de la famille de A._ ou de sociétés dont les ayants droit économiques étaient soit ce dernier ainsi que des membres de sa famille soit uniquement des membres de sa famille. Elle a invoqué avoir une action récursoire à l'encontre de A._ fondée sur les articles 218, 280 et 281 du Code civil taïwanais, subsidiairement sur les articles 50 et 51 du Code des obligations suisse, du fait de l'exécution de la sentence arbitrale du 29 avril 2010. I.b. Par ordonnance du 19 octobre 2011, le Tribunal de première instance du canton de Genève a ordonné le séquestre. I.c. Le 11 septembre 2012, il a admis l'opposition au séquestre formée par A._ et révoqué le séquestre. Il a considéré en bref que B._ SA n'avait pas rendu vraisemblable, tant en fait qu'en droit, l'existence de la créance récursoire. I.d. Par arrêt du 14 décembre 2012, la Cour de justice a admis le recours interjeté par B._ SA. Elle a considéré en substance que le premier juge avait donné à la notion de vraisemblance de l'existence de la créance une acception trop étroite, non conforme à celle requise par l'art. 272 al. 1 LP. Elle a annulé la décision entreprise sur ce point, et admis qu'à ce stade, la créance alléguée était vraisemblable, tant en ce qui concerne son existence que sa quotité. En bref, sous l'angle de la vraisemblance, B._ SA, qui avait été condamnée à payer - et avait payé - à Taïwan le montant des commissions versées à A._ en violation des dispositions contractuelles les liant, pouvait exiger, par hypothèse, la cession de la créance de Taïwan envers A._ résultant de la commission d'actes illicites par ce dernier. Cela étant, en raison du principe du double degré de juridiction qu'elle devait respecter, l'autorité cantonale a renvoyé la cause au premier juge pour qu'il statue sur les autres conditions du séquestre (art. 272 al. 1 ch. 2 et 3 LP). I.e. Dans le cadre de la procédure de renvoi, A._ a déposé des déterminations complémentaires sur faits nouveaux ainsi qu'un bordereau de pièces nouvelles, concluant à la révocation de l'ordonnance de séquestre du 19 octobre 2011. Se fondant sur l'avis de droit de l'Institut suisse de droit comparé du 28 mars 2013 et sur le jugement du 30 octobre 2012 du Tribunal de district de Taïpei déboutant la République de Chine (Taïwan) de toutes ses prétentions à son égard pour cause de prescription, il a notamment allégué que B._ SA ne pouvait disposer d'aucune créance récursoire à son encontre. I.f. Le 26 juin 2013, après avoir notamment déclaré irrecevables les faits nouveaux invoqués par A._, motif pris qu'ils se rapportaient à la question de la vraisemblance de la créance qui avait été définitivement tranchée dans l'arrêt de renvoi du 14 décembre 2012, le Tribunal de première instance a rejeté l'opposition au séquestre après examen des autres conditions posées par l'art. 272 al. 1 ch. 2 et 3 LP . I.g. La Chambre civile de la Cour de justice a confirmé ce jugement le 22 novembre 2013. J. Par écriture du 27 décembre 2013, A._ exerce un recours en matière civile contre l'arrêt du 14 décembre 2012 et celui du 22 novembre 2013. Il conclut principalement à leur annulation, à l'admission de son opposition au séquestre et à la révocation de l'ordonnance de séquestre du 19 octobre 2011. Il demande, subsidiairement, le renvoi de la cause à la Cour de justice pour nouvelle décision dans le sens des considérants et, plus subsidiairement, au Tribunal de première instance, ainsi que, dans tous les cas, le déboutement de B._ SA. L'intimée propose l'irrecevabilité du recours, subsidiairement, le rejet dans la mesure de sa recevabilité. La réplique du recourant lui a été communiquée. L'autorité cantonale se réfère aux considérants de son arrêt. K. Par ordonnance du 15 janvier 2014, le Président de la IIe Cour de droit civil a admis la requête de mesures provisionnelles en ce sens qu'il a ordonné à l'Office des poursuites du canton de Genève de surseoir à la continuation de la poursuite n o ggg en laissant le séquestre intact jusqu'à droit connu sur le présent recours. Par ordonnance du 11 mars 2014, le recourant a été invité à verser une sûreté en garantie des dépens, laquelle a été versée dans le délai imparti.