Faits : A. A.a. La société Z._ SA (ci-après: l'employeuse) était liée à X._ (ci-après: le travailleur) par un "contrat de collaboration" signé le 9 août 2000. Le 29 février 2008, les parties ont conclu une convention dactylographiée selon laquelle il avait été décidé, d'un commun accord entre elles, de mettre un terme au contrat "avec effet de ce jour"; le travailleur était autorisé à conserver 318 dossiers clients, sur lesquels l'employeuse renonçait à son droit de propriété. Le chiffre de 318 était apposé à la main et assorti de la mention manuscrite suivante: "sous réserve de quelques dossiers en cours non encore listés". A.b. En mai 2008, le travailleur a requis le transfert des portefeuilles de clients dont il pensait qu'ils lui avaient été cédés par l'employeuse. Cette dernière n'a pas procédé au transfert. A.c. Par courrier du 25 janvier 2011, le travailleur a élevé diverses prétentions vis-à-vis de l'employeuse, dont une indemnité pour licenciement abusif liée à la "non-reconnaissance du contrat de travail". B. B.a. Après avoir saisi l'autorité de conciliation le 1 er avril 2011, le travailleur (ci-après: le demandeur) a déposé une demande devant le Tribunal des prud'hommes du canton de Genève. Il concluait à la délivrance de divers documents et au paiement de 950'000 fr., soit 75'000 fr. bruts à titre de salaires pour les mois de mars à mai 2008, 150'000 fr. à titre d'indemnité pour licenciement abusif correspondant à six mois de salaire, 75'000 fr. à titre d'indemnité de vacances, 125'000 fr. à titre d'heures supplémentaires impayées, 75'000 fr. à titre de commissions et 450'000 fr. à titre d'indemnité pour les dossiers clients non transférés. Dans sa demande, le travailleur n'a consacré aucun allégué aux raisons de conclure la convention cessant les rapports contractuels avec effet immédiat. Il a simplement allégué en réplique que l'employeuse avait mis fin abruptement aux rapports contractuels le 29 février 2008, sans juste motif. L'employeuse (ci-après: la défenderesse) a contesté tout licenciement en faisant valoir que les parties avaient d'un commun accord signé une convention comportant des concessions réciproques. Elle n'a pas non plus indiqué quelles étaient les raisons de mettre fin immédiatement au contrat. B.b. Statuant par jugement du 4 août 2015, le Tribunal des prud'hommes a considéré que la défenderesse avait imposé au demandeur un licenciement immédiat injustifié. Il l'a condamnée à remettre au demandeur des certificats annuels de salaires (ch. 6 du dispositif) et à lui verser 39'292 fr. 55 bruts à titre de commissions et d'indemnité salariale (ch. 3), plus 85'948 fr. 80 nets à titre d'indemnité pour congé injustifié (ch. 5). Le Tribunal a invité la partie qui en avait la charge à opérer les déductions sociales légales usuelles (ch. 4) et a rejeté toutes autres conclusions (ch. 7). B.c. Les deux parties ont fait appel. Le demandeur a conclu à la réforme du chiffre 7 du dispositif du jugement attaqué, en ce sens que la défenderesse devait être condamnée à lui verser 450'000 fr. pour les dossiers clients non transférés. Par appel joint, la défenderesse a requis l'annulation du chiffre 5 du dispositif. Par arrêt du 3 mai 2016, la Chambre des prud'hommes de la Cour de justice genevoise a annulé le chiffre 5 du dispositif de la décision attaquée et, statuant à nouveau sur ce point, a débouté le demandeur de ses conclusions tendant au versement d'une indemnité de six mois de salaire. Elle a confirmé le chiffre 7 du dispositif. C. Le demandeur a interjeté un recours en matière civile au Tribunal fédéral, en concluant principalement à ce que la défenderesse soit condamnée à lui verser 85'948 fr. 80 nets et 450'000 fr., ou tout autre montant inférieur apprécié en équité, "à titre de prestation complémentaire résultant de la fin des rapports de travail". L'autorité intimée a déclaré se référer à son arrêt. La défenderesse a conclu à l'irrecevabilité du recours et, sur le fond, à son rejet.