Faits: A. Le 1 er mars 1999, la Banque Y._ SA (ci-après: la banque), ayant son siège à A._, a engagé X._, domicilié à B._, en qualité de gestionnaire de fortune, avec rang de directeur-adjoint, pour sa succursale de B._. Par la suite, les parties ont signé, le 11 août 2004, un nouveau contrat par lequel X._ a été chargé des relations avec la clientèle avec effet au 1er décembre 2004. Son salaire annuel a été fixé à 199'025 fr., payable en treize fois, avec un bonus. Lors d'un entretien avec son employeur qui eut lieu le 26 février 2007, X._, confronté à certains moyens de preuve, a reconnu que depuis 2003 il s'était livré à des malversations et avait prélevé des sommes en espèces qu'il avait utilisées pour ses besoins personnels. Il parlait alors de 400'000 fr. au maximum. Par courrier du 28 février 2007, la banque a licencié X._ avec effet immédiat. Le 28 mars 2007, la banque et X._, qui était assisté d'un avocat, ont signé une convention (ci-après: la convention du 28 mars 2007), par laquelle X._ autorisait la banque à vendre des actions lui appartenant et à transférer le produit de la vente sur un compte à disposition de la banque que cette dernière pourrait utiliser pour indemniser les clients et couvrir les frais liés aux malversations de l'employé. Selon l'art. 7 al. 1 de la convention, la banque était autorisée à débiter du compte d'indemnisation " tous les frais (internes et externes, y compris d'avocats et d'audit externe) encourus par la banque ensuite des procédures de vérification, de rétablissement des comptes et d'indemnisation des clients, ainsi que tous éventuels frais ou dépens liés à des procédures judiciaires qui seraient introduites contre la banque par des clients touchés qui n'accepteraient pas les conventions d'indemnisation ". L'art. 7 al. 2 ajoute que la banque débitera ses frais sur la base de " justificatifs (notes d'honoraires effectives des intervenants externes) et relevés d'heures d'intervention des services internes de la banque (selon un tarif horaire raisonnable) ". L'art. 8 prévoit que, s'il subsiste un solde à la fin du processus d'indemnisation, celui-ci serait restitué à X._. L'accord était soumis au droit suisse et le for judiciaire fixé à B._ (art. 10). En application de cet accord, les actions ont été vendues et le compte d'indemnisation a été créé et approvisionné à hauteur de 3'089'387 fr.25. Le 23 avril 2007, la banque a déposé une plainte pénale contre X._ pour abus de confiance et gestion déloyale. Par arrêt du 10 mars 2010, la Cour correctionnelle du canton de Genève a reconnu X._ coupable d'abus de confiance aggravé et l'a condamné à vingt-quatre mois de peine privative de liberté avec sursis pendant quatre ans, lui faisant interdiction d'exercer le métier de gérant de fortune durant quatre ans. La cour cantonale a retenu que X._ s'était enrichi par ses actes illicites à concurrence de 1'725'315 fr.60. La banque et X._ sont en litige sur la somme qui reste due entre eux. B. Le 23 décembre 2010, X._ a déposé à la juridiction des prud'hommes du canton de Genève une demande en paiement dirigée contre la banque, fondant ses prétentions d'une part sur le contrat de travail et d'autre part (et surtout) sur la convention du 28 mars 2007. La banque a conclu au déboutement et a pris des conclusions reconventionnelles. Par jugement du 21 mars 2012, le Tribunal des prud'hommes a condamné la banque à payer à X._ la somme brute de 32'105 fr.70 avec intérêts moratoires à 5% l'an dès le 28 février 2007 et la somme nette de 555'979 fr.55 avec intérêts moratoires à 5% l'an dès le 28 mars 2007, déboutant la banque de sa demande reconventionnelle et décidant de ne pas allouer de dépens. Les deux parties ont appelé de ce jugement. La banque a conclu principalement au déboutement de sa partie adverse. X._ a conclu à ce que l'art. 7 de la convention du 28 mars 2007 soit considéré comme nul et à ce que la banque soit condamnée, sur cette base, à lui payer 595'479 fr.84 avec intérêts à 5% dès le 28 mars 2007. Statuant par arrêt du 7 décembre 2012, la Chambre des prud'hommes de la Cour de justice a, pour l'essentiel, confirmé le jugement entrepris. Elle l'a réformé sur trois points qui concernent tous le solde dû à l'employé en vertu de la convention du 28 mars 2007 (selon le jugement de première instance: 555'979 fr.55 avec intérêts à 5% l'an dès le 28 mars 2007). Premièrement, elle a retenu qu'une note d'honoraires d'avocat de 15'332 fr.25 ne pouvait pas être débitée parce qu'elle était prise en compte deux fois. Deuxièmement, elle a admis qu'un débit de 8'000 fr. devait être écarté parce qu'il n'était pas suffisamment justifié, voire pris en compte deux fois. Ces deux points ne sont plus litigieux devant le Tribunal fédéral. Il en est résulté que le solde dû en capital de ce chef a été augmenté à 579'311 fr.80 par rapport au montant de 555'979 fr.55 retenu par le juge de première instance. Troisièmement, le point de départ de l'intérêt moratoire sur cette somme a été reporté au 23 décembre 2010 (au lieu du 28 mars 2007), la cour cantonale ayant estimé qu'une interpellation du débiteur était nécessaire et que celle-ci n'était intervenue que par le dépôt de la demande. C. X._ exerce un recours en matière civile au Tribunal fédéral contre l'arrêt cantonal du 7 décembre 2012. Invoquant une violation de l'art. 8 CC, de l'art. 9 Cst., ainsi que des art. 102, 321e et 341 CO, il conclut, sous suite de frais et dépens, à ce que sa partie adverse soit condamnée à lui verser la somme brute de 32'105 fr.70 avec intérêts à 5% l'an dès le 28 février 2007 et la somme nette de 595'479 fr.84 avec intérêts à 5% dès le 28 mars 2007; subsidiairement, il demande le renvoi de la cause à la cour cantonale. La banque intimée a conclu au rejet du recours avec suite de frais et dépens. Les parties ont répliqué et dupliqué.