Faits:
A. Y.A._ Holding SA avec siège à Genève a pour but social notamment la participation dans des sociétés, organisations ou institutions spécialisées dans le commerce des montres et des articles ou accessoires d'horlogerie. Y.B._ Ltd. est une société filiale de Y.A._ Holding SA dont le siège est à Singapour et dont le but social est la distribution des produits fabriqués par Y._ SA (anciennement Z._ SA). A l'époque des faits pertinents, V._ était président des conseils d'administration de Y.A._ Holding SA et de Y.B._ Ltd.
X._, citoyen anglais né en 1949, a été abordé par un tiers chargé de trouver un nouveau directeur pour les marchés Y._ d'Extrême Orient. Le profil ne mentionnait pas précisément qui serait l'employeur sinon par la mention de "Y._"; la personne de référence indiquée était "V._, Chief Executive, Z._ SA, Geneva". Par courrier du 10 août 1999 sur papier à en-tête de "Y.A._ Holding Genève", V._ a confirmé à X._ l'existence de discussions en cours, la référence du courrier mentionnant "CEO and Managing Director of Y.B._ Limited"; il était également précisé que le territoire concerné recouvrait la Malaisie, l'Indonésie et la Thaïlande.
Le 22 octobre 1999, l'administrateur de Y.A._ Holding SA et de Y.B._ Ltd., employant du papier à en-tête de "Y.A._ Holding Genève", a annoncé à X._ qu'il avait été engagé en qualité de "CEO et Managing Director de notre filiale Y.B._ Ltd." dès le 1er novembre 1999. Ce courrier indiquait le salaire en dollars de Singapour et le bonus, et précisait que Y.B._ Ltd. prendrait en charge les frais d'habitation et mettrait à disposition une voiture avec chauffeur. Dans la demande de permis de travail faite conjointement par X._ et Y.B._ Ltd., cette dernière figure sous la rubrique relative à l'employeur. Par la suite, Y.B._ Ltd. a versé le salaire de X._. Elle a loué, selon les termes du contrat de bail, un appartement pour son employé X._ et a payé le loyer. Elle a mis deux de ses voitures à disposition de X._ et payé une partie de ses dépenses personnelles ainsi que ses impôts.
Par lettre du 13 juin 2001 portant l'en-tête "Y.A._ Holding Genève", X._ a été informé qu'il avait été mis fin à son mandat de directeur de Y.B._ Ltd. avec effet au 12 juin 2001. Ce courrier était signé par W._ en sa double qualité d'administrateur de Y.A._ Holding SA et de Y.B._ Ltd.
B. Le 8 mai 2002, X._, domicilié en France, a saisi le Tribunal des prud'hommes du canton de Genève d'une demande tendant au paiement, par Y.A._ Holding SA, de la somme de 1'871'150 fr. avec intérêt à 5 % l'an dès le 1er juillet 2001, soit 580'500 fr. à titre de résiliation immédiate injustifiée, 1'064'250 fr. à titre de bonus pour la période du 1er novembre 1999 au 31 août 2001, 46'400 fr. à titre d'indemnités pour vacances non prises, 170'000 fr. à titre de frais de déménagement de Singapour à Paris et 10'000 fr. à titre de remboursement des billets d'avion de retour. Y.A._ Holding SA a contesté tant sa légitimation passive que l'ensemble des prétentions formulées.
Par jugement du 29 août 2008, le Tribunal a rejeté la demande au motif que Y.A._ Holding SA n'était pas l'employeur de X._ et n'avait donc pas la légitimation passive. Saisie par X._ et statuant par arrêt du 3 juin 2009, la Cour d'appel de la juridiction des prud'hommes du canton de Genève a confirmé le rejet de la demande.
C. X._ (le recourant) interjette un recours en matière civile au Tribunal fédéral, concluant principalement à ce que Y.A._ Holding SA soit condamnée à lui payer la somme de 1'871'150 fr. avec intérêt à 5 % l'an dès le 1er juillet 2001, avec suite de frais et dépens. Y.A._ Holding SA (l'intimée) propose le rejet du recours, sous suite de frais et dépens.

Considérant en droit:
1. Le recourant se plaint d'abord d'une violation de l'<ref-law>, plus précisément d'une violation du principe de la transparence. L'autorité cantonale a retenu que la relation de travail avait été formellement nouée avec la seule Y.B._ Ltd. Ce point n'est plus contesté. Par contre, le recourant soutient en substance que cette société singapourienne était entièrement contrôlée par l'intimée et agissait dans le plus strict respect de la volonté exprimée par celle-ci, cette volonté étant de surcroît exprimée par la même personne présidant le conseil d'administration des deux sociétés. Il en déduit que c'est de manière abusive que l'intimée a invoqué l'indépendance juridique de sa filiale, ce d'autant plus que n'étant pas résident permanent à Singapour, il ne serait pas en mesure d'y faire valoir ses droits à l'encontre de la filiale.
1.1 En matière internationale, la responsabilité découlant du principe de la transparence ("Durchgriff") est régie par le droit qui régit le statut de la société dominée (cf. art. 155 let. h LDIP; <ref-ruling> consid. 3.1; Vischer, in Zürcher Kommentar zum IPRG, 2e éd. 2004, n° 28 ad rem. prél. aux art. 150-165 LDIP; Dutoit, Commentaire de la loi fédérale du 18 décembre 1987, 3e éd. 2001, n° 8 ad art. 154 et n° 10 ad <ref-law>). Il s'agit en l'espèce, sous réserve des dispositions impératives du droit suisse (<ref-law>), du droit singapourien dont le Tribunal fédéral n'examine pas l'application, dès lors que la présente cause est de nature pécuniaire (<ref-law>). Le grief est ainsi irrecevable.
1.2 A supposer le droit suisse applicable, le grief ne pourrait néanmoins qu'être rejeté.
Selon le principe de la transparence déduit de l'<ref-law>, on ne peut pas s'en tenir sans réserve à l'existence formelle de deux personnes juridiquement distinctes lorsque tout l'actif ou la quasi-totalité de l'actif d'une société anonyme appartient soit directement, soit par personnes interposées, à une même personne, physique ou morale; malgré la dualité de personnes à la forme, il n'existe pas des entités indépendantes, la société étant un simple instrument dans la main de son auteur, lequel, économiquement, ne fait qu'un avec elle; on doit dès lors admettre, à certains égards, que, conformément à la réalité économique, il y a identité de personnes et que les rapports de droit liant l'une lient également l'autre; ce sera le cas chaque fois que le fait d'invoquer la diversité des sujets constitue un abus de droit ou a pour effet une atteinte manifeste à des intérêts légitimes. Mais l'indépendance juridique d'une société anonyme, même si elle n'a qu'un actionnaire unique, est néanmoins la règle, et ce n'est qu'exceptionnellement, soit en cas d'abus de droit, qu'il pourra en être fait abstraction (cf. <ref-ruling> consid. 2c p. 36; <ref-ruling> consid. 5a/aa; <ref-ruling> consid. 3.2).
Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>), et aucun fait nouveau ne peut être présenté à moins de résulter de la décision attaquée (<ref-law>); dans les affaires pécuniaires, il n'examine pas l'application du droit étranger (<ref-law>). En l'espèce, il ne ressort pas de la décision entreprise que le droit singapourien exclurait une demande en paiement de boni et interdirait au recourant d'ouvrir action contre la filiale de l'intimée devant les tribunaux de Singapour faute de statut de résident permanent dans cet État. Il ne peut pas être tenu compte de ces faits nouveaux (art. 99 al. 1 et <ref-law>).
L'intimée est une société holding classique avec de nombreuses filiales dans le monde entier. Le recourant était employé par la seule filiale à Singapour, entité juridique indépendante de droit singapourien, qui lui a versé salaire et autres indemnités durant son engagement, et il n'a travaillé que pour cette filiale. Dans ces circonstances, on ne discerne pas où résiderait l'abus de droit de la part de l'intimée à se prévaloir du fait que sa filiale est une entité juridique distincte. Qu'elle-même et la filiale avaient le même président du conseil d'administration, situation au demeurant nullement inhabituelle dans une structure de holding, est à cet égard sans pertinence; au surplus, il peut être renvoyé au considérant déterminant de l'arrêt querellé (cf. consid. 3.3.2).
2. Le recourant se plaint en second lieu d'une violation de l'<ref-law>, selon lequel celui qui promet à autrui le fait d'un tiers, est tenu à des dommages-intérêts pour cause d'inexécution de la part de ce tiers. Il soutient que l'intimée se serait engagée à ce que sa filiale lui verse les boni et paie les cotisations à une institution de prévoyance.
L'intimée objecte que le grief est irrecevable faute d'épuisement des voies de recours cantonales (<ref-law>). Il y a épuisement desdites voies lorsque la question de droit fédéral litigieuse a été soumise à la connaissance de la dernière instance cantonale qui, en vertu du droit de procédure cantonal, pouvait la revoir avec une cognition qui n'était pas plus restreinte que celle du Tribunal fédéral. Si l'autorité cantonale ne peut, selon ce droit de procédure cantonal, qu'examiner les griefs expressément soulevés, il n'y a épuisement des voies de recours cantonales que pour les griefs dont elle a été valablement saisie; si l'autorité cantonale a par contre le devoir ou simplement la possibilité d'examiner des questions de droit qui ne lui sont pas expressément soumises, le recourant peut soulever une question de droit pour la première fois devant le Tribunal fédéral (cf. <ref-ruling> consid. 1.3 p. 527 s.; <ref-ruling> consid. 1c; Corboz, in Commentaire de la LTF, n° 14 s. ad <ref-law>).
En l'occurrence, le recourant n'a pas soulevé le grief tiré de l'<ref-law> devant les instances cantonales. Ces autorités de la juridiction spéciale des prud'hommes sont uniquement compétentes pour juger des contestations entre employeurs et salariés pour ce qui concerne leurs rapports découlant d'un contrat de travail (art. 1 al. 1 let. a de la loi genevoise du 25 février 1999 sur la juridiction des prud'hommes [juridiction du travail; LJP/GE; RSG E 3 10]). Il apparaît que le porte-fort sort de ce cadre et le recourant ne tente pas de démontrer le contraire. Partant, les précédents juges ne pouvaient pas d'office examiner la question, si bien qu'il n'y a pas épuisement des voies de recours cantonales. Il s'ensuit l'irrecevabilité du grief, sans qu'il soit nécessaire d'examiner si le recourant se fonde sur des faits allégués à temps et constatés par les autorités cantonales.
3. Il résulte des considérants qui précèdent que le recours est irrecevable faute de grief recevable.
4. Compte tenu de l'issue du litige, les frais judiciaires et dépens de l'intimée sont mis à la charge du recourant, qui succombe (art. 66 al. 1 ainsi qu'art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. Les frais judiciaires, arrêtés à 10'000 fr., sont mis à la charge du recourant.
3. Une indemnité de 12'000 fr., à payer à l'intimée à titre de dépens, est mise à la charge du recourant.
4. Le présent arrêt est communiqué aux mandataires des parties et à la Cour d'appel de la juridiction des prud'hommes du canton de Genève.
Lausanne, le 16 octobre 2009
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Klett Cornaz