Faits:
A. A.a Au printemps 2003, Y._ a mandaté les avocats X._ à ... et A._ à ... aux fins de faire valoir ses droits dans la succession de son père, qui avait été à la tête de (...). Elle rencontrait des difficultés à établir le contenu de la masse successorale.
Les avocats ont mené une négociation globale qui a abouti le 19 décembre 2003 à la signature d'une proposition d'accord en vertu de laquelle Y._ (ci-après la mandante) devait hériter d'un patrimoine d'un peu plus de *** euros. Cette proposition impliquait pour les parties de renoncer définitivement à connaître la composition précise de la masse successorale. La mandante déclarait accepter de signer par gain de paix, tout en précisant qu'à ses yeux, certains chiffres retenus n'étaient pas conformes à la réalité.
Au cours de l'année 2003, la mandante s'est acquittée de deux notes d'honoraires établies par Me X._. La première, datée du 11 juin 2003, couvrait la période du 1er avril au 31 mai 2003 et s'élevait à 61'263 fr. 55, toutes taxes comprises (TTC). La deuxième, datée du 21 octobre 2003, se rapportait à l'activité déployée du 1er juin au 30 septembre 2003 et atteignait le montant de 129'148 fr. 95 TTC.
Le 10 février 2004, la mandante a rencontré ses deux conseils afin qu'ils lui expliquent les détails de l'accord définitif qu'elle s'apprêtait à signer. La question de leur rémunération a brièvement été évoquée; un montant de 25 millions d'euros a été demandé.
L'accord successoral final a été conclu le 18 février 2004. Il a été complété par un bref pacte successoral en date du 2 mars 2004.
Le 21 avril 2004, la mandante a donné l'ordre de verser 25 millions d'euros sur un compte auprès d'une banque ... dont Me X._ présidait le conseil d'administration. Cet avocat a prélevé 15'481'000 fr., correspondant au montant total d'une troisième note d'honoraires qu'il a établie en date du 29 avril 2004. Il affirme avoir mis le solde à disposition de son confrère Me A._. La mandante a apposé sa signature sur cette troisième facture.
A.b Le 16 novembre 2007, la mandante a déposé une requête en reddition de comptes à l'encontre de Me X._, à laquelle le Tribunal de première instance de Genève a donné suite. Le 21 janvier 2008, l'avocat a produit un rapport explicatif de quatre pages et le décompte des heures consacrées à l'exécution de son mandat. Il expliquait notamment que la mandante avait d'abord montré quelques hésitations face au montant de 25 millions d'euros demandés à titre d'honoraires, mais qu'elle avait finalement accepté cette proposition après qu'il eut réussi à lui procurer (...) euros supplémentaires dans l'accord successoral.
L'obtention de ce dernier montant est due à une seconde estimation des actifs d'un portefeuille fondée sur les monnaies dans lesquelles ils étaient investis et tenant compte d'une couverture de change. Une négociation à ce sujet était déjà en cours en décembre 2003, mais il n'est pas établi que la mandante en ait été informée à l'époque.
Par courrier du 25 février 2008, la mandante a déclaré invalider l'accord prétendument obtenu au sujet de la note d'honoraires du 29 avril 2004. Elle invoquait la lésion, l'erreur essentielle et le dol.
A.c Le 12 juin 2008, la mandante a saisi la Commission genevoise de taxation des honoraires d'avocat en lui demandant de réduire les trois notes d'honoraires de l'avocat X._. Par décision du 3 février 2009, cette autorité a déclaré la requête irrecevable au motif qu'elle était tardive.
La mandante a déféré cette décision à la cour de céans. Le recours en matière civile a été admis et la cause a été renvoyée à la Commission de taxation pour nouvelle décision. En bref, cette autorité s'est vu reprocher une application arbitraire du droit de procédure cantonal dès lors qu'elle avait déclaré tardive une requête pour laquelle la loi ne prévoyait pas de délai.
B. Au retour de la cause devant l'autorité cantonale, il a été convenu, en application de l'art. 40 de la loi genevoise du 26 avril 2002 sur la profession d'avocat (LPAv), que la Commission de taxation se constitue en Tribunal arbitral. Un acte de mission a été déposé le 16 octobre 2009 et une convention arbitrale a été signée le 28 octobre 2009.
Par sentence arbitrale du 10 décembre 2010, le Tribunal arbitral a confirmé les notes d'honoraires des 11 juin et 21 octobre 2003 et a arrêté la note du 29 avril 2004 à 4 millions d'euros. En conséquence, il a condamné Me X._ à rembourser à la mandante, en euros, la différence entre les montants perçus sur la note du 29 avril 2004 et la somme de 4 millions d'euros toutes taxes comprises, avec intérêts à 5% dès le 12 juin 2008.
En bref, le tribunal a considéré que la mandante était sous l'emprise d'une erreur essentielle (<ref-law>) et d'un dol (<ref-law>) lorsqu'elle avait accepté par actes concluants le contrat d'honoraires proposé le 10 février 2004. L'avocat n'avait pas informé sa cliente du fait qu'il n'avait pas réussi à définir la masse successorale totale en cause, tout en la convainquant des motifs justifiant d'accepter la transaction proposée. De surcroît, il ne l'avait pas correctement renseignée sur l'établissement de la note d'honoraires du 29 avril 2004, sur le nombre d'heures accomplies pour obtenir l'accord successoral et sur les motifs du versement supplémentaire de (...) euros; à cet égard, il avait tiré prétexte de l'accomplissement correct de son mandat pour obtenir une rémunération exceptionnelle de 25 millions d'euros. Le délai d'un an pour se prévaloir de ces vices du consentement avait commencé à courir le 21 janvier 2008, de sorte que la mandante avait agi en temps utile.
Le tribunal est arrivé à la conclusion que des honoraires globaux de 25 millions d'euros étaient excessifs et devaient être ramenés à 10 millions d'euros. Au regard de la clé de répartition interne pratiquée entre les deux conseils, l'avocat genevois avait droit à 2/5èmes de ce montant, soit 4 millions d'euros. Sur le principe, l'intimée avait droit à la répétition de l'indu. L'avocat n'avait pas été autorisé à prouver les faits propres à diminuer ou supprimer son obligation de restitution car ses allégations et offres de preuve étaient insuffisantes. Il restait tenu de rembourser la somme perçue en trop.
C. Contre cette décision, l'avocat X._ (ci-après: le recourant) a interjeté d'une part un recours au Tribunal fédéral, dans lequel il conclut à l'annulation de la sentence arbitrale, d'autre part un recours en nullité auprès de la Chambre civile de la Cour de justice genevoise.
Le 14 janvier 2011, la Présidente de la cour de céans a suspendu la procédure jusqu'à droit connu sur le recours en nullité cantonal.
Par arrêt du 23 septembre 2011, la Cour de justice a déclaré irrecevable le recours en nullité.
Le recourant a déféré cette décision au Tribunal fédéral le 25 octobre 2011, en concluant principalement à ce que le recours en nullité cantonal soit déclaré recevable et à ce que la cause soit renvoyée à la Cour de justice.
Invitée à se déterminer sur les deux recours déposés devant le Tribunal fédéral, la mandante (ci-après: l'intimée) a déposé une réponse se rapportant exclusivement au second recours du 25 octobre 2011, dont elle requiert le rejet.
Tant le Tribunal arbitral que la Cour de justice se réfèrent à leurs décisions respectives.
Par ordonnance du 21 novembre 2011, la Présidente de la cour de céans a octroyé l'effet suspensif aux deux recours.

Considérant en droit:
1. Les deux recours portent sur des décisions rendues dans la même cause successivement par un tribunal statuant en première instance, puis par un tribunal supérieur. Il se justifie dès lors de les traiter dans un seul arrêt.
Sera tout d'abord examiné le recours interjeté contre l'arrêt de la Cour de justice dès lors que son éventuelle admission pourrait à nouveau conduire à une suspension de la procédure afférente au recours dirigé contre la sentence arbitrale.
Recours contre l'arrêt de la Cour de justice du 23 septembre 2011
2. Le recours est dirigé contre une décision finale rendue par une autorité cantonale de dernière instance dans une cause ayant trait à l'exécution d'un mandat et aux honoraires d'un avocat, soit une cause de nature civile (cf. art. 72 al. 1, art. 75 al. 1 et 90 LTF). La valeur litigieuse minimale de 30'000 fr. est manifestement dépassée (<ref-law>) et le recours a pour le surplus été déposé dans le délai et la forme prescrits par la loi, de sorte qu'il est recevable sur le principe (art. 42 al. 1 et 2 LTF, art. 100 al. 1 en relation avec l'<ref-law>).
3. Le recourant reproche à la Cour de justice d'avoir violé les art. 1, 4 et 36 du concordat intercantonal sur l'arbitrage du 27 mars 1969 (ci-après: CA, ou le concordat) en refusant de considérer la décision du 10 décembre 2010 comme une sentence arbitrale susceptible d'être attaquée par un recours en nullité cantonal. La Cour de justice aurait en outre fait une application arbitraire du droit cantonal en considérant que l'art. 40 LPAv ne pouvait pas faire naître un arbitrage au sens du concordat.
3.1 Le Tribunal fédéral contrôle librement l'application du droit intercantonal, auquel ressortit le concordat précité (cf. art. 95 let. e et <ref-law>; YVES DONZALLAZ, Loi sur le Tribunal fédéral, Commentaire, 2008, n°s 3516 et 3518). En revanche, il ne revoit l'application du droit cantonal que si le recourant lie celle-ci à une violation du droit fédéral, en particulier s'il se plaint d'arbitraire dans l'application du droit cantonal (<ref-ruling> consid. 1.2). Le grief de violation du droit cantonal ou intercantonal est soumis aux exigences de motivation plus strictes de l'<ref-law>; l'acte de recours doit contenir un exposé succinct des droits ou principes violés et exposer de manière claire et circonstanciée en quoi consiste leur violation (<ref-ruling> consid. 1.2; <ref-ruling> consid. 2.2).
3.2 Depuis l'entrée en vigueur de la procédure civile fédérale le 1er janvier 2011, l'arbitrage interne est régi par les <ref-law> (RS 272). A juste titre, les parties ne prétendent pas que la nouvelle réglementation sur les recours (<ref-law>) entre en considération dès lors que la décision de la Commission de taxation constituée en Tribunal arbitral a été communiquée avant le 1er janvier 2011 (cf. <ref-law>; au surplus cf. infra, consid. 5.2).
Le concordat intercantonal, qui n'a désormais plus cours, s'appliquait à toute procédure par-devant un tribunal arbitral dont le siège se trouvait sur le territoire de l'un des cantons concordataires (art. 1 al. 1 CA). La sentence arbitrale pouvait être attaquée en nullité auprès du tribunal supérieur de la juridiction civile ordinaire du canton où se trouvait le siège de l'arbitrage (art. 36 CA en liaison avec l'art. 3 let. f CA); dans le canton de Genève, il s'agissait de la Cour de justice (art. 461 al. 1 de l'ancienne loi de procédure civile genevoise, ci-après aLPC). L'art. 36 CA était de droit impératif (art. 1 al. 3 CA).
Par arbitrage au sens du concordat, il fallait entendre tout mode conventionnel de règlement des litiges par des particuliers choisis directement ou indirectement par les parties et investis par elles du pouvoir de trancher à la place des juridictions étatiques normalement compétentes (JEAN-FRANÇOIS POUDRET, in Le droit de l'arbitrage interne et international en Suisse, 1989, p. 26 n° 1.2 ad art. 1 CA). En d'autres termes, le concordat visait les juridictions privées rendues par des particuliers auxquels l'ordre juridique permettait d'exercer une fonction en principe réservée à l'Etat (PIERRE JOLIDON, Commentaire du Concordat suisse sur l'arbitrage, 1984, p. 30).
3.3 Le Tribunal fédéral a dû se prononcer à plusieurs reprises sur le caractère arbitral ou étatique de diverses juridictions habilitées à rendre des sentences arbitrales dans des conflits de travail collectifs.
Dans une affaire où le droit cantonal permettait aux parties de saisir l'office cantonal de conciliation afin qu'il tranche leur différend par une "sentence arbitrale", le Tribunal fédéral a constaté que l'organe en question était institué par un arrêté de portée générale et qu'il était précisément chargé de juger des conflits tels que celui en cause; même si un accord préalable des parties était nécessaire pour saisir cette juridiction, il fallait considérer que la décision n'émanait pas d'un tribunal arbitral, mais bien d'une autorité cantonale (ATF 71 I 33).
Après l'entrée en vigueur du concordat sur l'arbitrage, la même réponse a été donnée à propos d'un office de conciliation qui, lorsqu'il statuait dans une activité "arbitrale" prévue par la loi cantonale, était constitué non seulement de ses trois membres permanents, mais aussi d'assesseurs désignés par les parties. Il a été jugé que cette collaboration des parties dans la désignation du tribunal n'enlevait rien au caractère étatique de celui-ci. Son noyau dur était constitué d'une institution étatique, soit l'office de conciliation, et la procédure était en grande partie réglée par la loi. Le concordat n'était dès lors pas applicable (arrêt P 216/76/mf du 9 février 1977 consid. 3c).
Alors que le droit cantonal en cause se limitait à satisfaire aux exigences minimales du droit fédéral en permettant aux parties de faire trancher leur litige par une sentence arbitrale contraignante de l'office de conciliation (cf. art. 34 et 35 de la loi fédérale sur le travail dans les fabriques - RS 821.41), il a été constaté que trois possibilités entraient en considération. Les parties pouvaient soit faire trancher le conflit de travail selon la procédure civile ordinaire, soit le soumettre à une autorité administrative étatique, à savoir l'office de conciliation, soit le porter devant un tribunal arbitral privé. Dans le cas concret, les parties avaient opté pour cette troisième solution, qui ne contrevenait ni au droit fédéral, ni au droit cantonal. Une clause de la convention collective prévoyait que l'office de conciliation statue sur les litiges relatifs à l'interprétation et l'application du contrat non pas en qualité d'office étatique, mais comme tribunal arbitral en lieu et place du juge civil ordinaire. L'office s'était qualifié pendant toute la procédure de tribunal arbitral contractuel sans que les parties n'émettent une objection (<ref-ruling>).
D'aucuns ont cru voir là un changement de jurisprudence (JOLIDON, op. cit., p. 60 s. n° 231 ad art. 1 CA). Le Tribunal fédéral a souligné que tel n'était pas le cas, en faisant observer qu'à l'<ref-ruling>, l'interprétation de la volonté des parties avait montré qu'elles entendaient sans équivoque instituer l'office de conciliation comme tribunal privé (arrêt 4P.98/1988 du 27 janvier 1989 consid. 4).
De manière générale, cette jurisprudence n'est pas remise en question par la doctrine (cf. JEAN-FRITZ STÖCKLI, Berner Kommentar, 1999, n° 87 ad <ref-law>; GABRIEL AUBERT, L'arbitrage en droit du travail, in Journée 1996 de droit du travail et de la sécurité sociale, vol. 16, 1999, p. 114 s.; ADRIAN STAEHELIN, Das öffentlich-rechtliche Schiedsgericht, in Privatrecht, Öffentliches Recht, Strafrecht, 1985, p. 389 ss; contra FRANK VISCHER/ANDREAS C. ALBRECHT, Zürcher Kommentar, 4e éd. 2006, n° 105 ad <ref-law>; JOLIDON, op. cit., p. 61 n° 231 ad art. 1 CA, est d'avis que les deux points de vue - tribunal étatique ou arbitral - sont défendables).
3.4 Il n'y a pas de motif de revenir sur la jurisprudence précitée. Il convient donc en bref de rechercher si la compétence du "tribunal arbitral" ayant rendu la sentence du 10 décembre 2010 est fondée sur la loi ou sur la seule volonté des parties.
4. 4.1 Dans sa teneur antérieure au 1er janvier 2011, qui est déterminante pour le cas concret, la LPAv prévoyait le système suivant: la Commission de taxation connaissait des contestations relatives au montant des honoraires et débours de l'avocat. Cette autorité était composée du président de la Cour de justice, du président du Tribunal de première instance et du bâtonnier; à défaut, un autre membre de ces juridictions, respectivement du Conseil de l'ordre, pouvait être désigné. Le secrétariat était assuré par le greffier de la Cour de justice (art. 36 aLPAv; art. 9 de l'ancien règlement d'application LPAv du 5 juin 2002).
La Commission de taxation se bornait à fixer le montant des honoraires et débours. Les questions relatives à l'existence et au montant de la créance, notamment celles ayant trait à l'exécution du mandat ou au règlement des comptes entre les parties, étaient du ressort du juge ordinaire (art. 39 al. 1 aLPAv). La Commission de taxation n'avait donc pas à examiner les griefs d'ordre matériel portant sur la manière dont l'avocat avait rempli son mandat; elle devait uniquement décider si les honoraires réclamés étaient proportionnés aux services rendus et conformes au tarif. Sa décision ne constituait pas un titre exécutoire, mais liait le juge civil (cf. arrêt P.23/1981 du 11 novembre 1981 consid. 4b, in SJ 1982 452). Elle ne pouvait être frappée de recours (art. 38 al. 2 aLPAv).
L'art. 40 aLPAv, intitulé "arbitrage", prévoyait une possibilité de déroger à cette scission procédurale (LAURA JACQUEMOUD-ROSSARI, La taxation des honoraires de l'avocat, in Défis de l'avocat au XXIe siècle, 2008, p. 296). Il avait la teneur suivante:
"1 Si les parties le requièrent et acceptent sa juridiction, la commission se constitue en tribunal arbitral et statue définitivement sur l'existence et le montant de la créance. Aucun recours n'est ouvert contre ses décisions.
2 En pareil cas, la commission détermine la procédure à suivre.
3 Les dispositions des articles 121 et 122 de la loi sur l'organisation judiciaire, du 22 novembre 1941, et celles de la loi de procédure civile, du 10 avril 1987, sont applicables par analogie en ce qui concerne la perception des frais d'arbitrage, qui comprennent les honoraires des arbitres et l'allocation de dépens."
Selon les travaux préparatoires, il s'agissait de simplifier la procédure et de permettre d'obtenir une décision définitive sur l'existence et le montant de la créance sans avoir à saisir le Tribunal civil du for du défendeur. Il était précisé que le recours en nullité prévu par le concordat intercantonal sur l'arbitrage était exclu; renvoi était fait à l'arrêt du Tribunal fédéral du 9 février 1977 (cf. supra, consid. 3.3; Mémorial du Grand Conseil, séance du 26 mai 1983, p. 1576).
4.2 L'arrêt de la Cour de justice retient en substance les éléments exposés ci-après.
Au retour de la cause devant l'autorité cantonale, les parties et la Commission de taxation, en application de l'art. 40 aLPAv, ont convenu que celle-ci se constitue en Tribunal arbitral. Dans un acte de mission du 16 octobre 2009, les parties ont désigné les arbitres comme étant la Commission de taxation constituée en Tribunal arbitral au sens de l'art. 40 LPAv; les trois membres composant cette commission étaient nommément cités. Le Tribunal arbitral devait déterminer la procédure en s'inspirant de la LPC.
Les parties ont signé une convention arbitrale le 28 octobre 2009, dans laquelle elles indiquaient accepter la compétence du Tribunal arbitral pour connaître du litige en tant qu'elle était basée, sans limitation de moyens, sur le mandat d'avocat confié au recourant, sur la conduite de ce mandat et sur les trois notes d'honoraires de juin et octobre 2003 et avril 2004. Les parties se référaient à la LPC à l'exclusion des règles prévues par le concordat sur l'arbitrage. Elles déclaraient applicable par analogie l'art. 31 de la loi genevoise sur l'organisation judiciaire, qui assimilait le Tribunal arbitral à une juridiction unique; en conséquence, la sentence rendue ne pouvait être soumise qu'à la connaissance du Tribunal fédéral.
Il ressort par ailleurs des pièces du dossier que le Tribunal arbitral était composé du Président de la Cour de justice, du Président du Tribunal de première instance et du Vice-bâtonnier. Les ordonnances et la sentence arbitrale ont été rédigées sur du papier dépourvu de signe officiel.
En définitive, l'autorité d'appel a constaté que la Commission de taxation avait statué en vertu de l'art. 40 aLPAv et que par cette réglementation, le législateur avait voulu mettre à disposition des parties une institution étatique nommée arbitrage pour résoudre définitivement le litige opposant un client à son avocat. Le législateur avait précisé que l'institution agissait comme autorité étatique et non comme tribunal arbitral privé, de sorte que le concordat sur l'arbitrage n'était pas applicable. Il fallait admettre qu'une telle solution était conforme à la jurisprudence fédérale.
4.3 La Cour de justice n'a pas méconnu la notion de tribunal arbitral au sens de l'art. 1 al. 1 CA et n'a pas appliqué arbitrairement le droit cantonal. Il ressort en effet du système légal exposé ci-dessus que le "Tribunal arbitral" statuant sur la base de l'art. 40 aLPAv ne fait qu'un avec la Commission de taxation, dont le caractère étatique ne fait aucun doute. La Commission voit simplement ses compétences élargies, en ce sens qu'elle peut, avec l'accord des parties, se prononcer sur des questions relevant normalement du tribunal civil ordinaire et statuer ainsi dans une seule décision sur le bien-fondé des honoraires et sur l'exécution du mandat, ce qui évite au mandant de devoir entamer une nouvelle procédure s'agissant du deuxième aspect. Conformément à la jurisprudence fédérale, le nécessaire consentement des parties pour saisir le "Tribunal arbitral" n'enlève rien au caractère étatique de cette juridiction qui tire sa compétence de la loi. Cet élément consensuel et la présence d'un avocat dans la composition du tribunal présentent des similitudes avec l'arbitrage privé, qui peuvent expliquer la terminologie employée par le législateur (cf. STEFAN VOGEL, Das öffentlich-rechtliche Schiedsgericht, ZBl 2010 671 s.; STAEHELIN, op. cit., p. 382 et 392 s.). Celle-ci n'est toutefois pas décisive.
Pour le surplus, le recourant tente d'attribuer aux réflexions faites dans les travaux préparatoires un sens qu'elles n'ont pas. Il y était clairement indiqué que le recours en nullité de l'art. 36 CA n'avait pas cours compte tenu de la jurisprudence de 1977 évoquée ci-dessus. A l'instar de la cour d'appel, il faut déduire de cette référence que la Commission de taxation constituée en Tribunal arbitral était considérée comme une autorité étatique et que le recours de l'art. 36 CA était exclu pour ce motif. Il importe peu que les travaux législatifs ne mentionnent pas l'<ref-ruling>, puisque cet arrêt ne consacre pas un revirement de jurisprudence. Le recourant se prévaut par ailleurs vainement de l'<ref-ruling>, lequel vise une situation différente; une autorité fédérale avait en effet été désignée comme tribunal arbitral alors qu'aucune base légale ne lui conférait la compétence de trancher le litige dans la situation donnée. Les travaux législatifs ne révèlent donc pas une ignorance de la jurisprudence fédérale ou du caractère impératif de l'art. 36 CA.
4.4 Le recourant fait encore grief à la Cour de justice d'avoir méconnu la portée du compromis résultant de l'acte de mission du 16 octobre 2009 et de la convention arbitrale du 28 octobre 2009. Les termes de ces deux actes ainsi que les circonstances postérieures à leur conclusion révéleraient que les parties, à l'instar de la situation jugée à l'<ref-ruling>, auraient voulu confier une mission d'arbitrage privé aux membres de la Commission de taxation.
Il est constant que dans l'acte de mission, les parties ont désigné comme arbitre la Commission de taxation constituée en Tribunal arbitral au sens de l'art. 40 aLPAv. Cet élément ressort aussi de la convention arbitrale, dont le recourant met en exergue certains passages, en particulier celui précisant que les parties acceptent "de constituer la Commission de taxation des honoraires d'avocat composée de Messieurs (...) [nom des 3 membres, réd.] en Tribunal arbitral au sens de l'art. 40 LPAv".
La référence expresse à l'art. 40 aLPAv signifie clairement que les parties ont voulu s'en remettre au système légal, lequel ne prévoit pas que les membres de la Commission de taxation statuent en qualité d'arbitres privés. L'on ne se trouve pas dans une situation telle que celle jugée à l'<ref-ruling>, où les parties avaient manifesté la volonté de confier une mission privée aux membres d'une autorité étatique. L'utilisation par les parties et les juges de termes tels que "tribunal arbitral", "sentence arbitrale" etc. n'est pas déterminante, puisqu'elle découle de la terminologie elle-même non décisive utilisée par le législateur. Cette ambiguïté résultant de la loi explique peut-être que la Commission de taxation, une fois constituée en Tribunal arbitral au sens de l'art. 40 aLPAv, ait utilisé du papier privé sans en-tête officielle. Quant au versement des avances de frais sur le compte bancaire ouvert au nom du secrétaire du tribunal, il faut constater qu'il s'agit de la solution prévue par la loi, laquelle précise que les frais d'arbitrage comprennent les honoraires des arbitres (art. 40 al. 3 aLPAv). Un tel système n'exclut pas le caractère étatique du tribunal, le canton étant libre de décider des modalités de rémunération de ses autorités. L'on peut ajouter que la loi impose l'application analogique des règles de la procédure ordinaire sur la perception des frais, assurant ainsi une rémunération modérée des "arbitres" et soustrayant cette question à la volonté des parties, à l'instar de ce qui prévaut pour les juridictions étatiques. Pour tous ces motifs, le grief doit être rejeté.
4.5 En bref, la Commission de taxation statuant sous un autre nom en vertu de l'art. 40 aLPAv ne constituait pas un tribunal arbitral au sens de l'art. 1 al. 1 CA. En conséquence, la règle de droit impératif de l'art. 36 CA imposant un recours en nullité cantonal ne trouvait pas application.
5. Dans une argumentation subsidiaire, le recourant observe que la Cour de justice était déjà saisie lorsque sont entrées en vigueur les dispositions de la LTF exigeant une double instance cantonale; pour se conformer aux art. 75 al. 2 et 130 al. 2 LTF, la cour aurait dû créer une voie de droit prétorienne.
5.1 La LTF impose aux cantons d'instituer des tribunaux supérieurs statuant comme autorités de recours de dernière instance, avec le même pouvoir d'examen que le Tribunal fédéral. Le recours en matière civile n'est en principe recevable que contre les décisions rendues par de telles instances (art. 75 et 111 al. 3 LTF). Les cantons disposaient d'un délai d'adaptation qui a expiré le 1er janvier 2011, date d'entrée en vigueur du CPC (<ref-law>). Dans un <ref-ruling> cité par le recourant, il a été jugé que sauf à violer le principe de primauté du droit fédéral (art. 49 Cst.), les cantons doivent soumettre au tribunal supérieur, c'est-à-dire au tribunal cantonal, les recours pendants au 1er janvier 2011 qui seront jugés après cette date (consid. 2.2 p. 240).
5.2 L'<ref-law> dispose que les recours sont régis par le droit en vigueur au moment de la communication de la décision aux parties. Par communication, il faut entendre la date de l'envoi de l'acte par le tribunal, un dispositif écrit étant suffisant (<ref-ruling> consid. 2).
En l'occurrence, la sentence arbitrale a été rendue le 10 décembre 2010 et notifiée aux parties le 13 décembre 2010; elle a donc été communiquée avant l'entrée en vigueur du CPC. Il s'ensuit que les voies de recours étaient régies par l'ancien droit cantonal. En l'occurrence, l'art. 40 al. 1 aLPAv excluait tout recours. L'<ref-law> n'était pas encore applicable compte tenu du délai d'adaptation octroyé par l'<ref-law>; la voie du recours en matière civile au Tribunal fédéral était donc ouverte contre cette décision rendue en instance cantonale unique. Légalement, il n'y aurait pas dû y avoir de recours cantonal pendant au moment de l'entrée en vigueur du CPC. L'<ref-ruling> ne saurait trouver application dans un tel cas de figure.
6. En définitive, c'est à juste titre que la Cour de justice a déclaré irrecevable le recours en nullité formé contre la sentence du 10 décembre 2010. Il s'ensuit que le recours en matière civile déposé le 25 octobre 2011 doit être rejeté.
Recours contre la sentence du Tribunal arbitral du 10 décembre 2010
7. 7.1 Le recours en matière civile est une voie de réforme (<ref-law>; cf. toutefois l'art. 77 al. 2 nLTF relatif à l'arbitrage). En conséquence, des conclusions tendant uniquement à l'annulation de la décision attaquée et au renvoi de la cause à l'instance cantonale sont en principe irrecevables (<ref-ruling> consid. 1.4.2). Le simple renvoi de la cause peut exceptionnellement être demandé s'il apparaît que le Tribunal fédéral, en cas d'admission du recours, ne serait pas en mesure de statuer lui-même sur le fond (<ref-ruling> consid. 3.1; sous l'ancienne OJ, cf. notamment <ref-ruling> consid. 1b; <ref-ruling> consid. 1). Les conclusions sont interprétées selon le principe de la confiance, à la lumière de la motivation du recours (<ref-ruling> consid. 1; <ref-ruling> consid. 2a).
7.2 Partant de la prémisse erronée que la décision du 10 décembre 2010 était une sentence arbitrale au sens du concordat, le recourant s'est contenté de prendre des conclusions cassatoires. En réalité, l'acte attaqué émane d'une autorité étatique et l'<ref-law> est applicable.
Cela étant, à la lecture des arguments développés dans le mémoire, l'on peut admettre que le recours est recevable. Certains griefs portant sur la violation de règles procédurales appelleraient de facto un renvoi à l'autorité précédente s'ils devaient être admis. L'on comprend en outre que le recourant veut faire constater l'incompétence du tribunal et qu'il conteste les vices de consentement retenus pour invalider l'accord sur la troisième note d'honoraires. Le recourant entend manifestement faire supprimer la condamnation l'obligeant à restituer une part de la rétribution touchée. Une telle volonté découle en particulier de la motivation étayant la requête d'effet suspensif formulée dans le même recours; le recourant y souligne les problèmes de recouvrement qu'il pourrait rencontrer si l'effet suspensif lui était refusé et si son recours était finalement admis.
8. 8.1 Invoquant l'art. 36 let. b CA, le recourant conteste tout d'abord que le tribunal arbitral ait été compétent pour prononcer une condamnation pécuniaire. Selon lui, la mission confiée aux arbitres consistait uniquement à établir le montant des notes d'honoraires, et non à ordonner la restitution d'un éventuel trop-perçu. En prenant une conclusion en ce sens dans son écriture du 29 mars 2010, l'intimée serait sortie du cadre compromissoire.
8.2 En matière d'arbitrage, la compétence du juge repose essentiellement sur la convention des parties. Constitue un motif de nullité au sens de l'art. 36 let. b ou c CA le fait pour le tribunal arbitral de statuer sur des points qu'il n'était pas habilité à connaître au regard du compromis arbitral. Dans le cas concret, le recourant considère à tort que la Commission de taxation était une autorité arbitrale au sens du concordat. En réalité, sa compétence découlait de l'art. 40 aLPAv, qui l'habilitait, moyennant l'accord des parties, à statuer définitivement sur l'existence et le montant de la créance. Au regard du but poursuivi par le législateur, qui était d'éviter aux parties de devoir procéder devant deux instances différentes, il n'était pas arbitraire d'admettre qu'une telle norme autorisait entre autres la Commission à ordonner la restitution des honoraires versés en trop. Le recourant ne dit du reste pas le contraire.
Compte tenu de la logique de l'art. 40 aLPAv, il paraît douteux qu'on puisse reconnaître aux parties la faculté d'opter pour une prorogation de compétence partielle, en ce sens que la Commission de taxation serait habilitée à statuer sur l'exécution du mandat, mais pas à ordonner la restitution des honoraires perçus en trop. Quand bien même une telle possibilité existerait, il faudrait constater que les parties n'ont pas manifesté la volonté d'en faire usage. Dans la convention arbitrale du 28 octobre 2009, les parties déclaraient accepter la compétence du tribunal en tant qu'elle se fondait, sans limitation de moyens, sur le mandat d'avocat confié au printemps 2003, sur la conduite du mandat et sur les trois notes d'honoraires émises par le recourant. L'acte de mission antérieur précisait que les arbitres devaient se prononcer sur chacune des conclusions des parties, après avoir tranché les allégations de l'intimée dans la mesure où cela était jugé utile et nécessaire. Or, le recourant a pris une conclusion en négation du droit de l'intimée au remboursement des honoraires et souligne lui-même qu'elle figurait dans l'acte de mission. Dans l'esprit des parties, la commission constituée en tribunal arbitral pouvait donc aussi être amenée à se prononcer sur la répétition des honoraires versés.
Il s'ensuit que le grief doit être rejeté.
9. Le recourant se plaint d'arbitraire dans l'établissement de deux faits ayant conduit à retenir que l'accord sur la troisième note d'honoraires était entaché de vices de la volonté.
9. Le recourant se plaint d'arbitraire dans l'établissement de deux faits ayant conduit à retenir que l'accord sur la troisième note d'honoraires était entaché de vices de la volonté.
9.1 9.1.1 Tout d'abord, il serait inexact d'affirmer que l'intimée ignorait les incertitudes planant sur la composition de la masse successorale. Cette constatation serait contredite par les allégations concordantes des parties et ne reposerait au surplus sur aucune pièce.
9.1.2 Selon l'état de fait retenu par le tribunal, l'intimée a accepté la proposition négociée par son conseil malgré les doutes qu'elle conservait au sujet des éléments de fortune recueillis, qu'elle jugeait insuffisants; elle pensait que ses avocats avaient obtenu à ce sujet le maximum de renseignements possibles. Le recourant n'avait pas réussi à définir la masse successorale totale en cause et ne prouvait pas avoir tenu sa cliente informée de ce fait, alors qu'il l'avait convaincue des motifs justifiant qu'elle accepte la transaction proposée.
9.1.3 Le recourant ne prétend pas que le tribunal aurait méconnu de façon arbitraire une disposition de droit cantonal régissant les aveux. Par ailleurs, l'allégation prétendument concordante de l'intimée porte essentiellement sur le défaut d'information quant à la portée juridique de la transaction successorale, plainte qu'elle émet à titre rétrospectif; l'on ne saurait en tirer des conclusions quant à l'état de ses connaissances sur la masse successorale au moment de la transaction. Cela étant, le tribunal n'a pas ignoré les doutes que l'intimée nourrissait à ce sujet, mais il a reproché plus précisément au recourant d'avoir entretenu l'intimée dans la croyance erronée que ses avocats avaient obtenu le maximum de renseignements possibles; le recourant ne cherche pas à remettre en cause cet élément. Son grief se révèle infondé.
9.1.3 Le recourant ne prétend pas que le tribunal aurait méconnu de façon arbitraire une disposition de droit cantonal régissant les aveux. Par ailleurs, l'allégation prétendument concordante de l'intimée porte essentiellement sur le défaut d'information quant à la portée juridique de la transaction successorale, plainte qu'elle émet à titre rétrospectif; l'on ne saurait en tirer des conclusions quant à l'état de ses connaissances sur la masse successorale au moment de la transaction. Cela étant, le tribunal n'a pas ignoré les doutes que l'intimée nourrissait à ce sujet, mais il a reproché plus précisément au recourant d'avoir entretenu l'intimée dans la croyance erronée que ses avocats avaient obtenu le maximum de renseignements possibles; le recourant ne cherche pas à remettre en cause cet élément. Son grief se révèle infondé.
9.2 9.2.1 Le tribunal aurait en outre constaté arbitrairement que la négociation destinée à procurer (...) euros supplémentaires à l'intimée était déjà en cours en décembre 2003; en réalité, elle n'aurait débuté qu'à la fin du mois de janvier 2004, comme l'attesterait une pièce du dossier cantonal.
9.2.2 La pièce en question est une note manuscrite datée du 28 janvier 2004, qui indique notamment "Portefeuille transformé en Euro. Date sera communiquée". Un tel document est tout au plus susceptible d'attester que le recourant avait connaissance de cette possibilité de "gain" supplémentaire à la fin du mois de janvier 2004, ce qui n'exclut pas encore qu'une négociation ait été en cours en décembre 2003. A cet égard, le tribunal mentionne un échange de correspondances entre le recourant et un autre avocat genevois les 19 et 23 décembre 2003; référence est faite à des pièces spécifiques du dossier. Le recourant n'explique pas en quoi l'appréciation fondée sur ces preuves serait arbitraire. Il se contente d'affirmer que le tribunal ne s'est appuyé sur aucune preuve et se réfère à ses observations du 19 septembre 2008. Une telle motivation ne satisfait pas aux exigences requises s'agissant du grief d'arbitraire dans l'établissement des faits (cf. <ref-ruling> consid. 1.4.3). Il s'ensuit que le second grief relatif à l'état de fait doit aussi être rejeté.
9.3 Le recourant ne conteste l'application des art. 24 et 28 CO qu'en tant qu'elle reposerait sur un état de fait erroné. Le rejet des moyens de fait prive d'objet le grief de droit.
10.
10.1 Le recourant se plaint d'un manque de clarté du dispositif de la sentence arbitrale en tant qu'il le condamne à rembourser à l'intimée, en euros, la différence entre les montants perçus sur la note du 29 avril 2004 et la somme de 4 millions d'euros TTC. Le recourant dit ne pas saisir la portée des termes "montants perçus". S'agit-il de 10 millions d'euros, qui équivaudraient aux 15'481'000 fr. réclamés dans la note du 29 avril 2004? Si tel était bien le cas, il aurait été aisé de le dire, de sorte que l'idée du tribunal devait être autre. S'agit-il alors des montants perçus par l'étude du recourant? Ou de ceux touchés par le recourant personnellement?
10.2 Selon un principe général de procédure, le dispositif doit être formulé de façon suffisamment précise pour qu'il puisse être exécuté tel quel et que l'autorité compétente n'ait plus qu'à vérifier si les conditions pour l'exécution sont remplies, sans avoir à trancher des questions de droit qui relèvent de l'autorité de jugement (cf. <ref-ruling> consid. 3.3; <ref-ruling> p. 93; <ref-ruling> consid. 6).
En l'occurrence, la formulation du dispositif n'indique pas quel montant précis le recourant doit restituer à l'intimée. La lecture de la sentence n'apporte pas non plus de réponse évidente. Il en ressort en effet que sur les 25 millions d'euros versés par l'intimée, le recourant a prélevé 15'481'000 fr. TTC correspondant à sa note d'honoraires du 29 avril 2004 et "affirme avoir mis le solde à disposition" de son confrère. Plus loin, le tribunal précise ne pas avoir de motif de modifier la clé de répartition entre les deux avocats telle qu'elle se dégage de ces éléments, à savoir le montant global versé et le montant revendiqué par le recourant dans sa note du 29 avril 2004. Aux yeux du tribunal, le recourant est-il réputé enrichi des 15'481'000 fr. indiqués dans sa note du 29 avril 2004, montant qui devrait être converti en euros? Ou de 25 millions d'euros? Ou d'un autre montant? A supposer qu'une question de change monétaire ait conduit le tribunal à s'abstenir d'indiquer un chiffre précis, il faudrait observer que le taux de conversion est un fait notoire que le juge peut sans autre prendre en considération (<ref-ruling> consid. 4.1 p. 90).
Au vu du manque de précision du dispositif, il convient d'annuler l'arrêt en application de l'<ref-law> et de renvoyer la cause à l'autorité précédente afin qu'elle indique clairement quel montant en euros le recourant doit rembourser.
11.
11.1 Le recourant reproche encore au Tribunal arbitral d'avoir violé diverses règles de l'ancienne LPC et d'avoir enfreint des principes généraux de procédure. Il aurait été indûment privé de la possibilité d'établir qu'il n'était plus enrichi des montants perçus.
11.2 L'art. 40 al. 2 aLPAv laissait à la Commission de taxation constituée en Tribunal arbitral la compétence de déterminer la procédure à suivre. Comme le relève le recourant, l'acte de mission prévoyait que le Tribunal arbitral s'inspire de la LPC, tandis que la convention de procédure ultérieure déclare cette loi applicable. Pour l'issue de la cause, il n'est pas nécessaire d'examiner plus avant dans quelle mesure le renvoi implique une application stricte de la loi concernée. Il sied par ailleurs de rappeler que le Tribunal fédéral ne peut contrôler l'application du droit cantonal que si le recourant lie celle-ci à une violation du droit fédéral, de sorte que les griefs ne répondant pas à cette exigence ne seront pas examinés (cf. supra, consid. 3.1).
11.3
11.3.1 Le recourant se plaint d'une violation du principe de la bonne foi en ce sens que le tribunal l'a laissé procéder sans lui signaler dans l'ordonnance du 8 juin 2010 que ses allégations quant à la persistance de l'enrichissement étaient insuffisantes. En taisant ce problème à ce stade de la procédure d'une façon contraire à l'art. 215 al. 1 aLPC, le tribunal aurait perdu la possibilité de l'invoquer ultérieurement. Il aurait encore conforté le recourant dans son erreur en occultant ce problème dans l'ordonnance du 6 octobre 2010 et en justifiant son refus d'auditionner les témoins proposés par d'autres motifs que ceux finalement retenus dans sa sentence. Le recourant aurait ainsi renoncé en méconnaissance de cause à faire entendre un témoin et à plaider.
11.3.2 L'art. 215 al. 1 aLPC requiert que l'ordonnance admettant l'enquête par témoins énonce les faits à prouver, lesquels doivent être précis et concluants. Les commentateurs soulignent que si cette double condition relative aux allégations n'est pas satisfaite, le droit à la preuve ne sera pas ouvert. Ainsi, avant d'ordonner l'administration de la preuve par témoins, le juge devra résoudre la question préalable de la précision et de la pertinence des allégués. Il n'est certes pas lié par son ordonnance, mais le principe de la bonne foi s'oppose à ce qu'il autorise tout d'abord une partie à rapporter la preuve d'un allégué et qu'il lui reproche ensuite de n'avoir pas satisfait aux exigences de l'art. 215 al. 1 aLPC (BERTOSSA/GAILLARD/GUYET/SCHMIDT, Commentaire de la loi de procédure civile du canton de Genève, vol. II, n° 1 s. ad <ref-law>).
11.3.3 En l'occurrence, le tribunal a rendu une ordonnance le 8 juin 2010 par laquelle il invitait simplement les parties à produire leur liste de témoins. Le recourant ne prétend pas que ce mode de faire, consistant dans un premier temps à interpeller les parties sur les témoins qu'elles voulaient faire auditionner, procéderait d'une application arbitraire du droit cantonal. Le tribunal, qui n'ordonnait pas encore formellement l'administration de la preuve, pouvait sans arbitraire s'épargner de trancher la question de savoir si les allégations étaient suffisamment précises et pertinentes. Après avoir pris connaissance des témoins proposés par les parties, le tribunal a indiqué dans une ordonnance du 6 octobre 2010 qu'en raison des qualités des témoins et des principes liés à l'appréciation anticipée des preuves, il renonçait à procéder aux enquêtes sollicitées, pour des motifs qui seraient exposés dans la sentence à intervenir. Il a maintenu et développé ces motifs dans son jugement du 10 décembre 2010. Il y a par ailleurs expliqué qu'il incombait au bénéficiaire d'un enrichissement illégitime de prouver les faits propres à diminuer ou supprimer son obligation de restitution (<ref-law>) et qu'en l'occurrence, le recourant n'avait pas été amené à rapporter une telle preuve au motif que ses allégations y relatives étaient insuffisantes, tout comme ses offres de preuve.
Le tribunal n'a donc pas modifié sa position juridique ni adopté une attitude contradictoire, mais il n'a informé le recourant de l'insuffisance de ses allégations qu'au stade du jugement. En maxime des débats, les parties sont responsables de l'allégation des faits. La loi de procédure peut alléger ce fardeau en prévoyant un devoir ou un pouvoir d'interpellation du juge. A l'époque, cette question ressortissait au droit cantonal (cf. <ref-ruling> consid. 1; <ref-ruling> consid. 2d p. 340; FABIENNE HOHL, Procédure civile, tome I, 2001, n°s 754 et 770). Or, sous réserve de son argumentation fondée sur l'art. 215 al. 1 aLPC, le recourant ne soutient pas qu'une règle du droit genevois imposant un tel devoir ou pouvoir au juge aurait arbitrairement été méconnue. En définitive, on ne saurait reprocher au tribunal d'avoir contrevenu au principe de la bonne foi en n'attirant pas l'attention du recourant, au demeurant avocat et assisté d'un conseil, sur l'insuffisance de ses allégations.
11.4
11.4.1 Le recourant se plaint encore d'une violation des principes de l'immutabilité de l'objet du litige et de la bonne foi. Dans la mesure où il était admissible d'étendre l'objet du litige à la question du remboursement du trop-perçu, le tribunal aurait à tout le moins dû indiquer aux parties si elles devaient concentrer leurs moyens dans une seule écriture ou si elles pouvaient compter sur un deuxième débat à propos de cette nouvelle question.
11.4.2 Le principe d'immutabilité de l'objet du litige ou de simultanéité des moyens d'attaque et de défense impose aux parties de présenter leurs moyens en une seule fois à un stade donné de la procédure. Il est en règle générale assorti d'atténuations. Avant 2011, cette question relevait du droit de procédure cantonal; les cantons déterminaient librement à quel stade du procès les moyens devaient être formulés (cf. HOHL, op. cit., n°s 806-808 et 813; le même auteur, L'immutabilité de l'objet du litige, in Unification de la procédure civile, 2004, p. 31 s.).
11.4.3 En l'occurrence, il est constant que le tribunal arbitral a ordonné un second échange d'écritures à la requête de l'intimée. Dans sa réplique, celle-ci a complété ses conclusions en demandant le remboursement d'honoraires perçus en trop. Le recourant ne cite aucune disposition du droit genevois régissant le nombre d'échange d'écritures, respectivement le moment où il est encore possible d'introduire des allégations et conclusions. Le sort du grief est ainsi scellé.
Remarques finales
12. En définitive, le recours contre l'arrêt de la Cour de justice du 23 septembre 2011 est rejeté. Le recours contre la sentence arbitrale du 10 décembre 2010 est partiellement admis. Cette décision est annulée en vertu de l'<ref-law> et la cause renvoyée au Tribunal arbitral pour qu'il précise son dispositif dans la mesure indiquée ci-dessus.
Le recourant succombe entièrement sur le recours dirigé contre l'arrêt de la Cour de justice. Il doit ainsi assumer les frais judiciaires y relatifs et verser une indemnité de dépens à l'intimée, qui s'est déterminée sur ce recours (art. 66 al. 1 et art. 68 al. 1 et 2 LTF).
Quant au recours visant la sentence du Tribunal arbitral, le recourant perd sur la majorité de ses griefs, mais obtient gain de cause sur une question d'imprécision du dispositif, dont les parties ne sont pas responsables. Le recourant doit ainsi assumer l'émolument judiciaire sauf sur la question du dispositif, pour laquelle aucun émolument ne peut être mis à la charge de l'intimée. Le canton de Genève est dispensé de verser des dépens au recourant dans la mesure où le développement du grief n'occupe pas de place particulière au regard du recours pris dans son ensemble. Quant à l'intimée, elle a renoncé à se déterminer sur ce second recours, de sorte qu'elle ne peut prétendre à aucune indemnité de ce chef.
En définitive, un émolument judiciaire de 30'000 fr. est mis à la charge du recourant. Des dépens par 17'000 fr. sont alloués à l'intimée.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours formé contre l'arrêt rendu le 23 septembre 2011 par la Chambre civile de la Cour de justice du canton de Genève est rejeté.
2. Le recours formé contre la sentence arbitrale rendue le 10 décembre 2010 par le Tribunal arbitral avec siège à Genève est partiellement admis. La décision attaquée est annulée et la cause est renvoyée à l'autorité précitée pour qu'elle précise son dispositif dans le sens des considérants.
3. Un émolument judiciaire de 30'000 fr. est mis à la charge du recourant.
4. Le recourant versera à l'intimée une indemnité de 17'000 fr. à titre de dépens.
5. Le présent arrêt est communiqué aux mandataires des parties, au Tribunal arbitral avec siège à Genève et à la Cour de justice du canton de Genève.
Lausanne, le 28 mars 2012
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
La Greffière: Monti