Faits : A. A.a. Par contrat de bail à loyer daté du 8 décembre 2009, les bailleresses B1._, B2._ et B3._ SA ont convenu de céder l'usage d'un appartement de 6,5 pièces à Genève aux locataires L1._ et L2._. Le loyer mensuel a été fixé à 6'000 fr. plus 250 fr. de charges. Le bail devait durer du 16 décembre 2009 au 31 décembre 2012. A.b. En janvier 2012, les locataires ont sollicité une baisse de loyer en raison de la baisse du taux hypothécaire. Par courrier du 31 janvier 2012, cette réduction leur a été refusée au motif que le bail était de durée déterminée. Par la même missive, les bailleresses ont informé les locataires qu'elles n'étaient pas disposées à conclure un nouveau bail au terme de celui en cours. Le 15 février 2012, les locataires ont sollicité une prolongation de bail de quatre ans et une baisse de loyer correspondant à la baisse du taux hypothécaire. Dans l'hypothèse où le bail ne serait pas renouvelé, ils demandaient à pouvoir bénéficier d'une résiliation facilitée moyennant un préavis d'un mois pour le 15 ou la fin d'un mois. La régie immobilière mandatée par les bailleresses a répondu le 27 février 2012 qu'une résiliation anticipée serait acceptée à la condition qu'un candidat de remplacement solvable soit proposé, en précisant ce qui suit: (...) vous avez signé un bail à terme fixe qui se termine le 31 décembre 2012. Pour tenir compte des instructions reçues de nos mandants, nous vous confirmons que nous ne sommes pas autorisés à conclure un nouveau bail au-delà de cette date. En cas de restitution anticipée de la chose louée, nous appliquerons l'art. 9 des conditions générales et règles et usages locatifs, à savoir que le délai d'un mois pour le 15 ou la fin d'un mois sera accepté, à compter de la date à laquelle nous serons en possession du dossier d'un candidat solvable disposé à signer un bail aux mêmes conditions, accompagné des documents permettant de vérifier sa solvabilité. » A.c. Le 13 juillet 2012, les locataires ont résilié le bail pour le 14 août 2012 et ont proposé deux locataires de remplacement, à savoir L3._ et son épouse d'une part, et L4._ et L5._ d'autre part. Dans les fiches d'inscription de la régie, L3._ était présenté comme un diplomate de nationalité israélienne ayant pris ses fonctions à la Mission permanente d'Israël au mois de juillet 2012 et disposant d'un revenu mensuel brut de 20'000 fr. Etaient notamment annexées au dossier une copie de son passeport et une attestation de la Mission permanente d'Israël à Genève confirmant ce qui précède. Quant à L4._ et L5._, ils étaient respectivement de nationalité américaine et canadienne et effectuaient des démarches pour obtenir le permis B. L4._ était un trader appelé à prendre ses fonctions à Genève le 1er août 2012, et dont le revenu annuel brut s'élevait à 225'000 fr. Son employeur le décrivait comme une personne sérieuse et de confiance. Avec cette candidature était transmise la copie d'un courrier que l'agence de location mandatée par ces deux personnes avait adressé le 12 juillet 2012 à la régie des bailleresses. Il en ressortait que les deux prénommés avaient exprimé un fort intérêt pour cet objet et souhaitaient faire une demande de location ferme et définitive aux conditions suivantes: - bail à loyer de 5 ans indexé avec possibilité de résiliation annuellement à chaque date d'anniversaire de bail dès la fin de la première année, - loyer mensuel CHF 6'250.- plus CHF 250.- de charges + parking inclus, - bail au nom de Monsieur L4._ et Madame L5._, - début du bail au 15.08.12 ou à convenir, - garantie bancaire standard, - clause libératoire: le locataire ou l'occupant qui, pour des raisons liées à sa vie professionnelle, quitte la Suisse pourra résilier son bail, moyennant un préavis écrit de trois mois pour la fin d'un mois, à l'exception de l'échéance du 31 décembre. Cette faculté ne pourra être exercée qu'à partir de la deuxième année de location. A.d. Par courrier du 16 juillet 2012, les bailleresses ont averti les locataires que les dossiers des candidats proposés ne satisfaisaient pas aux exigences légales et n'étaient dès lors pas acceptables. Elles constataient que le dossier de L3._ ne comportait pas d'attestation de non-poursuite ni de déclaration écrite selon laquelle le bail serait repris jusqu'au 31 décembre 2012. Le dossier de L4._ et L5._ présentait les mêmes carences. Le 2 août 2012, les locataires ont répondu que L4._ et L5._ ne pouvaient transmettre une attestation de non-poursuite car ils étaient peu auparavant domiciliés à l'étranger. Quant à L3._, il bénéficiait d'une immunité de poursuite due à son statut de diplomate, de sorte qu'il se trouvait également dans l'impossibilité de fournir cette attestation. De plus, les locataires proposés présentaient des revenus supérieurs à ceux des locataires actuels. Quant à l'exigence d'une déclaration écrite de reprise du bail jusqu'au 31 décembre 2012, il s'agissait d'un non-sens, car il était évident que les locataires proposés souhaitaient rester à Genève pour une durée indéterminée. Les locataires ont contesté le refus des bailleresses en le qualifiant d'abusif. Ils ont quitté les locaux le 14 août 2012 et ont restitué les clés aux bailleresses. Ils ont payé le loyer et les charges jusqu'au 15 août 2012, versant la somme de 3'125 fr. pour le mois d'août 2012. Le 14 août 2012, les bailleresses ont confirmé leur position et ont précisé que la remise des clés ne libérait pas les locataires de leurs obligations. B. B.a. Après avoir saisi l'autorité de conciliation le 21 août 2012, les bailleresses ont déposé une demande le 2 novembre 2012 devant le Tribunal des baux et loyers du canton de Genève. Elles concluaient à ce que le Tribunal constate que le contrat de bail est de durée déterminée avec échéance au 31 décembre 2012, et à ce qu'il condamne les locataires à payer 3'263 fr. de loyer et charges pour le mois d'août 2012, puis 6'000 fr. de loyer mensuel et 250 fr. de charges mensuelles dès le mois de septembre 2012 jusqu'au 31 décembre 2012. Parallèlement, les locataires ont déposé le 5 novembre 2012 une demande visant à ce que le Tribunal des baux et loyers constate qu'ils sont libérés, avec effet au 15 août 2012, du contrat de bail et de toutes obligations contractuelles y relatives, les sûretés versées devant être libérées en leur faveur. Les deux causes ont été jointes. B.b. Les bailleresses ont indiqué que l'appartement avait été reloué dès le 1er mars 2013 pour un loyer mensuel de 5'450 fr., charges non comprises, et pour une durée échéant le 28 février 2015. Elles ont précisé que l'appartement avait été offert à la location dès la fin du mois de juillet 2012. Le Tribunal a notamment entendu un employé de la régie mandatée par les bailleresses qui avait été chargé de relouer l'appartement litigieux à la suite de la résiliation du bail. Ce témoin a déclaré que la régie avait interpellé les candidats proposés par les locataires pour savoir s'ils étaient prêts à reprendre le bail aux mêmes conditions, soit avec une échéance au 31 décembre 2012. Dans son souvenir, les deux candidats avaient répondu par la négative. La pratique des bailleresses dans cet immeuble consistait à conclure des baux à termes fixes, étant précisé qu'à l'échéance, un nouveau bail aurait pu être négocié. Le témoin a encore précisé que conformément à la pratique, la régie avait publié dès le début du mois d'août 2012 une annonce sur son site Internet pour relouer l'appartement. Celui-ci avait été reloué en mars 2013 à un loyer inférieur, soit 5'450 fr. par mois. Selon le témoin, ce type d'objet était difficile à louer en raison du loyer. Il se rappelait qu'un des candidats était diplomate, ce qui pouvait poser des problèmes de responsabilité en cas de défaut de paiement. Il a encore précisé que si l'un des candidats avait accepté de reprendre le bail au loyer de 6'000 fr. jusqu'au 31 décembre 2012 tout en proposant un loyer inférieur pour la suite, la régie aurait pu entrer en matière; du moins était-ce la pratique générale de la régie, indépendamment du cas d'espèce. Le Tribunal a également auditionné deux employés de l'agence de relocation mise en oeuvre par les époux L4._ et L5._. Ceux-ci avaient été informés qu'ils devaient reprendre le bail des locataires sortants aux mêmes conditions; ils avaient affirmé qu'ils n'auraient certainement pas accepté de reprendre un bail pour une durée déterminée de quatre mois. Toutefois, selon l'un des témoins, l'usage dans le cas d'une durée résiduelle courte était de reprendre le bail pour la durée restante avec un engagement de renouveler le contrat au-delà de cette durée, soit au même loyer, soit à des conditions différentes. Ni L3._, ni les époux L4._ et L5._ n'ont pu être auditionnés comme témoins. B.c. Par jugement du 31 août 2015, le Tribunal des baux et loyers a constaté que les locataires étaient libérés de toute obligation découlant du contrat de bail dès le 15 août 2012. Il a déclaré irrecevable leur conclusion en libération de sûretés et débouté les bailleresses de toutes leurs conclusions. Le Tribunal a considéré en bref que les motifs invoqués par les bailleresses pour refuser les candidats présentés par les locataires étaient dénués de tout fondement. Une attestation de non-poursuite ne pouvait être réclamée de la part de personnes précédemment domiciliées à l'étranger ou titulaires d'une immunité diplomatique. Quant à l'exigence d'une déclaration écrite selon laquelle le bail ne serait repris que pour la durée résiduelle de quatre mois, soit jusqu'au 31 décembre 2012, elle relevait de l'abus de droit, compte tenu de la pratique de la régie en la matière, et du fait que l'appartement litigieux avait été reloué dès le 1er mars 2013 à un loyer inférieur. B.d. Statuant par arrêt du 25 avril 2016, la Chambre des baux et loyers de la Cour de justice du canton de Genève a rejeté l'appel formé par les bailleresses et confirmé le jugement du 31 août 2015. C. Les bailleresses ont saisi le Tribunal fédéral d'un recours en matière civile et d'un recours constitutionnel subsidiaire visant à réformer l'arrêt du 25 avril 2016, en ce sens que leurs conclusions pécuniaires prises en première instance devraient être intégralement admises et les conclusions prises en première instance par les locataires intégralement rejetées. L'autorité précédente a déclaré se référer à son arrêt. Les locataires ont conclu au rejet du recours en matière civile et à l'irrecevabilité du recours constitutionnel subsidiaire.