Faits:
A.
En 2006, la société Z._ SA s'est fait céder l'usage de locaux commerciaux situés en ville de Genève, moyennant un loyer mensuel de 8'250 fr. Le contrat de bail à loyer pouvait être résilié pour le 31 mars 2009 en respectant un préavis de six mois, puis tous les deux ans, soit pour le 31 mars 2011, 31 mars 2013 et ainsi de suite.
En février 2010, la locataire a présenté au bailleur X._ une société disposée à reprendre le contrat avec effet au 1er avril 2010. Le bailleur s'y est opposé, au motif que la candidate n'offrait pas des conditions de solvabilité suffisantes.
Le 23 avril 2010, la locataire a réaffirmé son intention de résilier le bail de manière anticipée et déclaré qu'elle se considérait libérée de ses obligations dès le 1er juin 2010. Elle a suggéré qu'un état des lieux soit effectué au plus tard le 31 mai 2010. Le 19 mai, elle a demandé la fixation d'une date pour l'état des lieux en précisant qu'à défaut de réaction, elle restituerait les clés le 31 mai.
A la date annoncée, soit le 31 mai 2010, la locataire a libéré les locaux et remis les clés à la régie chargée de gérer l'immeuble.
Le 9 août 2010, une réunion s'est tenue dans les locaux, en présence notamment du bailleur et de deux représentants de la locataire. Cette séance avait pour but d'établir un état des lieux de sortie. Le procès-verbal établi sur place mentionnait des travaux à la charge de la locataire. Il ne comportait aucune signature pour le compte de celle-ci. Le 11 août 2010, le bailleur a adressé ce document à la locataire, qui a confirmé son refus de signer au motif que l'état des lieux avait été fait tardivement, et que les dégradations constatées provenaient de l'usure normale des locaux.
Le bailleur a mandaté un huissier qui a établi un nouvel état des lieux le 13 août 2010.
Après que le bailleur eut procédé à des travaux, les locaux ont été reloués dès le 1er octobre 2010.
B.
B.a. Le 15 juillet 2010, la locataire a déposé une requête devant l'autorité de conciliation; elle a ensuite saisi le Tribunal des baux et loyers du canton de Genève par demande du 11 octobre 2010. Dans ses conclusions, elle invitait le tribunal à constater qu'elle était libérée de toute obligation découlant du bail dès le 31 mai 2010, respectivement à ordonner la libération de la garantie de loyer.
Par réponse du 11 janvier 2011, le bailleur a conclu à ce qu'il soit constaté que la locataire était libérée de ses obligations dès le 31 octobre 2010. A titre reconventionnel, il a requis le paiement des montants suivants:
- 47'305 fr. 50 à titre de loyers et charges pour la période du
1er juin au 15 novembre 2010,
- 322 fr. 80 pour ses frais de constat par huissier,
- 45'366 fr. 30 pour les travaux de remise en état des locaux,
- 20 fr. à titre de frais non spécifiés,
- 5'616 fr. 70 pour les frais de recherche d'un nouveau locataire. Il a en outre requis une indemnité non chiffrée pour ses frais d'avocat avant procès.
Par jugement du 2 novembre 2012, le Tribunal des baux et loyers a constaté que la locataire était libérée de ses obligations à compter du 30 septembre 2010. Il l'a condamnée à payer au bailleur 28'200 fr. à titre de loyers et charges pour les mois de juin à septembre 2010 ainsi que 1'000 fr. pour les frais de recherche d'un nouveau locataire. Il a rejeté toutes autres conclusions.
S'agissant des frais de remise en état, le tribunal a jugé que l'avis de défauts était tardif. Le bailleur avait récupéré la jouissance exclusive des locaux le 31 mai 2010, date à laquelle toutes les clés avaient été restituées à la régie. Les locaux avaient été vidés de tout meuble, objet ou accessoire, à l'exception d'un carton et de quelques câbles électriques laissés dans le local informatique. En procédant à un état des lieux le 9 août 2010, alors qu'il pouvait disposer des locaux depuis plus de deux mois, le bailleur n'avait pas respecté l'incombance découlant de l'<ref-law>. En conséquence, il était déchu du droit de réclamer le remboursement des travaux chiffrés à 45'366 fr. 30. Quant aux frais d'huissier (322 fr. 80), ils avaient été engagés en vain.
B.b. Le bailleur a déposé un appel auprès de la Chambre des baux et loyers de la Cour de justice. En sus des montants alloués en première instance, il prétendait au paiement de 45'366 fr. 30 pour les frais de remise en état des locaux, respectivement de 322 fr. 80 pour les frais de constat par huissier. La Chambre a rejeté l'appel et confirmé la décision attaquée par arrêt du 7 août 2013.
C.
Le bailleur saisit le Tribunal fédéral d'un recours en matière civile, dans lequel il conclut principalement à l'annulation de l'arrêt et au renvoi de la cause à l'autorité précédente pour qu'elle rende une nouvelle décision; à titre subsidiaire, il reprend les conclusions formulées en appel, en ce sens qu'il entend faire condamner la locataire au paiement de 45'366 fr. 30 et 322 fr. 80, en sus des montants alloués par les juges genevois.
La locataire conclut au rejet du recours. L'autorité précédente se réfère à son arrêt.

Considérant en droit:
1.
La valeur litigieuse minimale de 15'000 fr. requise pour les litiges en matière de bail à loyer est manifestement atteinte (<ref-law>). Le recours répond de surcroît aux autres conditions de recevabilité.
2.
Le bailleur dénonce une violation des art. 264, 267 et 267a CO. En substance, il plaide qu'il n'y a pas eu restitution de la chose louée dans la mesure où les locaux n'ont pas été entièrement vidés; par conséquent, le délai pour vérifier la chose louée ne pouvait pas commencer à courir.
2.1.
L'<ref-law> régit la restitution anticipée de la chose louée. Le locataire qui restitue la chose sans respecter le terme de congé est libéré de ses obligations à condition qu'il présente un remplaçant solvable que le bailleur ne puisse raisonnablement refuser. A défaut, le locataire reste tenu de payer le loyer jusqu'au prochain terme de congé. Toutefois, le bailleur doit admettre l'imputation des impenses qu'il a pu épargner et des profits qu'il a pu retirer d'un autre usage de la chose louée.
En vertu de l'<ref-law>, le locataire doit restituer la chose dans l'état qui résulte d'un usage conforme au contrat. La loi ne définit pas l'acte de restitution en soi, mais précise partiellement quelle qualité doit revêtir la chose louée lorsqu'elle est restituée (cf. Peter Higi, Zürcher Kommentar, 4e éd. 1995, nos 5, 81 et 85 ad <ref-law>). Selon la doctrine et la jurisprudence, la restitution se fait par remise de la chose même ou des moyens qui la font passer dans la puissance du bailleur ( HANS PETER WALTER, in OR: Art. 1-529, HONSELL éd., 2008, n° 3 ad <ref-law>); ainsi, lorsque le bail porte sur des locaux, le locataire doit remettre tous les jeux de clés servant à y accéder, y compris les éventuels doubles qu'il a fait faire (arrêt 4C.224/1997 du 17 février 1998 consid. 3a, in mp 1998 182; cf. entre autres CAROLE AUBERT, in Droit du bail à loyer, BOHNET/MONTINI éd., 2010, n° 3 ad <ref-law>; HIGI, op. cit., n° 13 ad <ref-law>).
L'application de l'<ref-law> suppose que le locataire manifeste clairement et sans ambiguïté son intention de restituer la chose au bailleur de façon anticipée. Le locataire doit procéder effectivement à la restitution complète et définitive. Il ne peut se contenter de laisser les locaux vides et inoccupés, mais doit en remettre les clés au bailleur (arrêt 4A_220/2008 du 7 août 2008 consid. 3, traduit in mp 2009 21; cf. aussi 4C.129/1999 du 5 octobre 1999 consid. 2a, in DB 2000 n° 13 p. 22).
Jurisprudence et doctrine soulignent parfois que la restitution des locaux n'intervient que lorsque le locataire a restitué toutes les clés et entièrement vidé les pièces (cf. arrêts 4A_456/2012 du 4 décembre 2012 consid. 2.1, in SJ 2013 I 525; 4C.224/1997 précité, consid. 3a; BISE/PLANAS, in Droit du bail à loyer, op. cit., n° 13 ad <ref-law>; DAVID LACHAT, La restitution anticipée de la chose louée [<ref-law>]: questions choisies, in CdB 1998 135, cité dans un arrêt du Tribunal cantonal fribourgeois publié in CdB 1999 95; PASCAL TERRAPON, La restitution des locaux loués et l'offre d'un locataire de remplacement, in 12 e Séminaire sur le droit du bail, Neuchâtel 2002, p. 7).
Le locataire qui enfreint ses devoirs en matière de restitution découlant de l'<ref-law> doit des dommages-intérêts en application de l'<ref-law>. Le bailleur peut notamment obtenir le remboursement des frais qu'il a dû assumer si le locataire a omis de vider et/ou de nettoyer les locaux (arrêt 4A_456/2012 précité, consid. 2.1; cf. aussi 4C.261/2006 du 1 novembre 2006 consid. 3.2.3); en effet, l'on attend en principe du locataire qu'il vide entièrement les locaux et les nettoie (cf. HIGI, op. cit., n os 89 et 92 ad <ref-law>).
2.2.
2.2.1. Le recourant reproche à l'autorité précédente d'avoir méconnu l'exigence d'une restitution complète et effective, impliquant que les locaux soient entièrement vidés de leur contenu. Dans la mesure où des objets subsistaient dans l'une des pièces, la cour cantonale aurait dû conclure que la locataire n'avait pas restitué la chose louée.
2.2.2. La locataire a voulu se libérer du bail avant le terme contractuel du 31 mars 2011. Dans une telle situation, elle devait signifier clairement au bailleur son intention de quitter les locaux de façon anticipée et concrétiser cette intention par des actes.
En l'occurrence, la locataire a proposé en février 2010 une candidate acceptant de reprendre le bail le 1er avril 2010. Le 23 avril, la locataire a fait savoir que malgré le refus opposé par le bailleur, elle s'estimait déliée de toute obligation à compter du 1er juin 2010; elle a demandé qu'un état des lieux soit effectué avant cette date. Le 19 mai, elle a annoncé qu'elle remettrait de toute façon les clés à la régie le 31 mai. A cette date, elle a effectivement restitué l'intégralité des clés. Elle a en outre vidé les lieux. Toutefois, il subsistait des câbles et un carton dans le local informatique. Selon la cour cantonale, il n'a pas pu être démontré à qui appartenait ce matériel.
Au vu de ce qui précède, l'intention de restituer les locaux a été clairement exprimée, et suivie d'actes concrets. Les quelques objets trouvés dans un local, à supposer qu'ils appartiennent à la locataire, ne sauraient en aucun cas faire douter de sa volonté de quitter les lieux. Dans ce contexte, le bailleur qui avait recouvré la maîtrise exclusive de la chose louée devait procéder à la vérification de son état pour dénoncer d'éventuels manquements de la locataire. La présence des objets pouvait tout au plus engager la responsabilité contractuelle de la locataire pour d'éventuels frais d'enlèvement, que le recourant n'a pas fait valoir.
La Cour de justice n'a donc pas enfreint le droit fédéral en considérant que la chose louée avait été restituée. Il reste à examiner si le bailleur a vérifié l'état de la chose louée et donné l'avis des défauts en temps utile.
2.3.
2.3.1. L'<ref-law> a la teneur suivante:
1 Lors de la restitution, le bailleur doit vérifier l'état de la chose et aviser immédiatement le locataire des défauts dont celui-ci répond.
2 Si le bailleur néglige de le faire, le locataire est déchargé de toute responsabilité, à moins qu'il ne s'agisse de défauts qui ne pouvaient pas être découverts à l'aide des vérifications usuelles.
3 Si le bailleur découvre plus tard des défauts de ce genre, il doit les signaler immédiatement au locataire.
Le bailleur doit procéder à la vérification lors de la restitution effective, voire immédiatement après ( HIGI, op. cit., n° 14 ad <ref-law>). Il doit aviser "immédiatement" le locataire des défauts dont celui-ci répond. Selon la doctrine, l'avis doit en règle générale être donné dans les deux ou trois jours ouvrables après la restitution ( HIGI, op. cit., n° 33 ad <ref-law>; Walter, op. cit., n° 12 ad <ref-law>), voire une semaine après (Le droit suisse du bail à loyer, Commentaire SVIT, 2011, n° 35 ad art. 267-267a CO; HANNES ZEHNDER, Die Mängelrüge im Kauf-, Werkvertrags- und Mietrecht, RSJ 2000 547 s.). D'aucuns soulignent qu'il faut tenir compte des circonstances du cas concret ( LACHAT, Le bail à loyer, 2008, p. 805 note 20 en bas de page; cf. ROGER WEBER, in Basler Kommentar, 5 e éd. 2011, n° 3 ad <ref-law>). Selon les pratiques cantonales, l'avis donné trois semaines ou un mois après la remise des locaux est en principe tardif ( AUBERT, op. cit., n° 17 ad <ref-law> et les arrêts cités). La cour de céans a jugé tardif un avis intervenu environ deux mois après le changement de sous-locataire (arrêt 4A_589/2012 du 21 novembre 2012 consid. 2.2).
2.3.2. En l'occurrence, la locataire a restitué les clés le 31 mai 2010. Les parties ont effectué un état des lieux le 9 août 2010. Deux jours après, le bailleur a adressé à la locataire le procès-verbal d'état des lieux que celle-ci n'avait pas voulu signer. Il s'est ainsi écoulé un peu plus de deux mois entre la remise des clés et l'état des lieux, respectivement l'avis des défauts.
Le recourant objecte qu'en date du 29 juillet 2010, les parties se sont mises d'accord pour effectuer un état des lieux le 9 août 2010. Il estime que l'avis a été donné en temps utile, puisqu'il a été notifié deux jours après l'état des lieux contradictoire.
L'argument est erroné. D'après les faits retenus, la locataire a vainement demandé à deux reprises qu'un état des lieux soit effectué au plus tard le 31 mai 2010, date à laquelle elle a effectivement restitué la chose louée en remettant à la régie la totalité des clés. Le simple fait que la locataire ait accepté deux mois plus tard de fixer une réunion "a[yan]t pour but d'établir un état des lieux de sortie", puis ait participé quelques jours plus tard à une telle séance, ne permet pas d'inférer qu'elle renonçait ainsi à invoquer la tardiveté de la vérification et de l'avis des défauts.
En bref, la Cour de justice n'a pas enfreint le droit fédéral en considérant que la vérification de la chose louée, et partant l'avis des défauts étaient intervenus tardivement. Le recourant ne conteste pas qu'un tel cas de figure prive le bailleur du droit de rechercher le locataire en responsabilité pour d'éventuels défauts, ce qui suffit déjà à clore toute discussion (cf. <ref-law>; <ref-ruling> consid. 2.2.1).
2.4. Au vu de ce qui précède, les prétentions fondées sur les frais de remise en état (45'366 fr. 30) ne peuvent qu'être rejetées, tout comme la demande d'indemnisation pour les frais d'huissier (322 fr. 80).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
Un émolument judiciaire de 2'000 fr. est mis à la charge du recourant.
3.
Le recourant versera à l'intimée une indemnité de 2'500 fr. à titre de dépens.
4.
Le présent arrêt est communiqué aux mandataires des parties et à la Chambre des baux et loyers de la Cour de justice du canton de Genève.
Lausanne, le 7 janvier 2014
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
La Greffière: Monti