Faits : A. Par contrat de bail du 26 février 2003, le locataire X._ a pris à bail un appartement de quatre pièces sis à Genève. Le loyer a été fixé à 2'280 fr. par mois, charges comprises; il est demeuré inchangé. Par avis comminatoire du 20 août 2014, adressé sous pli recommandé non réclamé par le locataire, la (nouvelle) bailleresse Z._ l'a mis en demeure de lui régler dans les trente jours le montant de 4'538 fr. 05 à titre d'arriérés de loyer et de charges pour les mois de juillet et août 2014, ainsi que de frais de rappel (90 fr.) et de mise en demeure (50 fr.), sous déduction d'un acompte de 161 fr. 95. Elle lui a signifié qu'à défaut de paiement intégral de la somme réclamée dans le délai imparti, elle résilierait le bail conformément à l'art. 257d CO. Considérant que le montant indiqué n'avait pas été intégralement réglé dans le délai fixé, la bailleresse a, par avis officiel du 1 er octobre 2014, résilié le bail pour le 30 novembre 2014. Ce formulaire mentionnait une mise en demeure du 30 novembre 2014 et un arriéré de loyer de 9'120 fr. pour la période du 1 er juillet au 31 octobre 2014. Dans la lettre d'accompagnement, la bailleresse a indiqué faire suite à la lettre recommandée qu'elle avait adressée au locataire le 20 août 2014. La résiliation n'a pas été contestée par le locataire. Ensuite d'une demande du locataire, un arrangement de paiement a été convenu le 20 janvier 2015, portant sur le remboursement de la somme de 9'120 fr. en quatre mensualités de 2'280 fr., à payer du 1 er février au 1 er mai 2015, en sus des indemnités pour occupation illicite. Par courrier du 9 mars 2015, la bailleresse a écrit au locataire que l'arrangement suscité n'était pas respecté, les mensualités des 1 er février et 1 er mars n'ayant pas été honorées; elle a sollicité le versement de 4'560 fr. à réception de sa missive, à défaut de quoi une procédure en évacuation serait introduite. Le 1 er juin 2015, la bailleresse a fixé au locataire un état des lieux de sortie au 30 juin 2015. Elle a ensuite introduit une première requête en évacuation qui a été déclarée irrecevable. B. Par requête en protection de cas clair déposée le 15 décembre 2015, la bailleresse a derechef requis l'évacuation immédiate du locataire et l'exécution directe du jugement. Le locataire a conclu à l'irrecevabilité, objectant que la résiliation était nulle: l'avis de résiliation faisait référence à une mise en demeure du 30 novembre 2014 qui était inexistante, et un nouveau contrat de bail avait été conclu tacitement entre les parties. Par jugement du 3 février 2016, le Tribunal des baux et loyers du canton de Genève a condamné le locataire à évacuer l'appartement et autorisé la bailleresse à requérir l'évacuation par la force publique. Le locataire a saisi la Chambre des baux et loyers de la Cour de justice genevoise. Par arrêt du 25 avril 2016, cette autorité a confirmé le jugement du 3 février 2016. C. Le locataire (ci-après: le recourant) a interjeté un recours en matière civile concluant à ce que la requête de la bailleresse (ci-après: l'intimée) soit déclarée irrecevable. Il a sollicité l'effet suspensif. L'intimée a conclu à ce que la demande d'effet suspensif soit rejetée et le recourant débouté de toutes autres ou contraires conclusions. L'autorité précédente s'est référée à son arrêt. Par ordonnance du 29 juin 2016, la présidente de la cour de céans a accordé l'effet suspensif au recours.