Sachverhalt:
A.
A._ (Mieter, Beschwerdeführer) war ab Frühling 1993 Mieter eines Büros am U._weg in V._ sowie eines Garagenplatzes in derselben Überbauung. Ab 1. Januar 2000 mietete er ausserdem einen Einzelgaragenraum an der W._strasse in V._ (nachfolgend "Spritzenhäuschen" genannt, da es sich um das ehemalige Depot für die Feuerwehrspritze handelt).
In der Folge kaufte die B._ AG (Vermieterin, Beschwerdegegnerin) die Liegenschaften, in denen sich die Mietobjekte befinden. Die Mietverhältnisse gingen auf sie über (<ref-law>).
Die Parteien stehen in einem Streit betreffend die Miete des Spritzenhäuschens.
B.
Nach dem Scheitern der Schlichtungsverhandlung reichte der Mieter am 6. November 2019 beim Bezirksgericht Horgen, Mietgericht, Klage ein und beantragte, die Vermieterin sei zu verpflichten ihm "unter dem Titel Mietzinsreduktion und Schadenersatz infolge Einschränkung der Gebrauchstauglichkeit des Mietobjekts" insgesamt Fr. 54'253.-- nebst Zins ab 30. Juni 2014 zu bezahlen.
Zur Begründung machte er geltend, er habe das Spritzenhäuschen als Lagerraum für seinen im Büro am U._weg betriebenen Handel mit Oldtimer-Ersatzteilen genutzt. Durch nasse Wände im Spritzenhäuschen hätten die Ersatzteile einen Schaden erlitten, für den die Vermieterin gemäss <ref-law> hafte.
Die Vermieterin bestritt die sachliche Zuständigkeit des Mietgerichts und trug auf Nichteintreten an. Daraufhin wurde das Verfahren auf die Einrede der Unzuständigkeit beschränkt. Mit Beschluss vom 17. September 2020 trat das Mietgericht mangels sachlicher Zuständigkeit nicht auf die Klage ein.
Dagegen erhob der Mieter Berufung an das Obergericht des Kantons Zürich und erneuerte seine erstinstanzlichen Anträge. Eventualiter beantragte er die Rückweisung an die Erstinstanz zur materiellen Beurteilung. Mit Urteil vom 26. November 2020 wies das Obergericht die Berufung ab und bestätigte den Beschluss des Mietgerichts Horgen.
C.
Der Beschwerdeführer erhebt gegen dieses Urteil Beschwerde in Zivilsachen mit den Anträgen, das Urteil des Obergerichts aufzuheben und das Mietgericht für "sachlich und örtlich zuständig" zu erklären und anzuweisen, die Klage materiell zu behandeln. Eventualiter sei die Sache zur Sachverhaltsergänzung und neuen Entscheidung an die Vorinstanz zurückzuweisen. Zudem seien die erst- und zweitinstanzlichen Kosten dem Beschwerdegegner aufzuerlegen, und dieser zur Bezahlung einer angemessenen Parteientschädigung für das erst- und zweitinstanzliche Verfahren zu verpflichten.
Die Beschwerdegegnerin beantragte, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Obergericht verzichtete auf Vernehmlassung.
Der Beschwerdeführer replizierte.

Erwägungen:
1.
Der angefochtene Entscheid des Obergerichts ist ein Endentscheid (<ref-law>) einer Vorinstanz im Sinne von <ref-law>. Weiter übersteigt der Streitwert den nach <ref-law> geltenden Mindestbetrag von Fr. 15'000.--. Die Beschwerde in Zivilsachen ist damit grundsätzlich zulässig.
2.
2.1. Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, ansonsten darauf nicht eingetreten werden kann (<ref-ruling> E. 2 S. 116; <ref-ruling> E. 2.1). In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Unerlässlich ist dabei, dass auf die Begründung des angefochtenen Entscheids eingegangen und im Einzelnen aufgezeigt wird, worin eine vom Bundesgericht überprüfbare Rechtsverletzung liegt. Die beschwerdeführende Partei soll in der Beschwerde an das Bundesgericht nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2 S. 116).
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den streitgegenständlichen Lebenssachverhalt als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (<ref-ruling> E. 1.3.1 mit Hinweisen). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 117; <ref-ruling> E. 1.5). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein können (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Die Partei, welche die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 1.3.1 S. 18 mit Hinweisen). Wenn sie den Sachverhalt ergänzen will, hat sie zudem mit präzisen Aktenhinweisen darzulegen, dass sie entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (<ref-ruling> E. 2 S. 90).
2.3. Soweit die Parteien die vorinstanzliche Beweiswürdigung kritisieren, ist zu beachten, dass das Bundesgericht in diese nur eingreift, wenn sie willkürlich ist. Willkür liegt nach der Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls in Betracht zu ziehen oder gar vorzuziehen wäre, sondern bloss, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 4.1; <ref-ruling> E. 2.1; je mit Hinweisen). Die Beweiswürdigung ist mithin nicht schon dann willkürlich, wenn sie nicht mit der Darstellung der beschwerdeführenden Partei übereinstimmt, sondern bloss, wenn sie offensichtlich unhaltbar ist (<ref-ruling> E. 4.1; <ref-ruling> E. 4.2.1). Dies ist dann der Fall, wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat (<ref-ruling> E. 2.3; <ref-ruling> E. 4.2; <ref-ruling> E. 4.2). Inwiefern die Beweiswürdigung willkürlich sein soll, ist in der Beschwerde klar und detailliert aufzuzeigen (BGE <ref-ruling> E. 2.2). Namentlich genügt es nicht, einzelne Beweise anzuführen, die anders als im angefochtenen Entscheid gewichtet werden sollen, und dem Bundesgericht in appellatorischer Kritik die eigene Auffassung zu unterbreiten, als ob diesem freie Sachverhaltsprüfung zukäme (vgl. <ref-ruling> E. 2.3).
3.
Streitig ist, ob das Mietgericht Horgen sachlich zuständig ist.
3.1. Nach <ref-law> regelt das kantonale Recht die sachliche und funktionelle Zuständigkeit der Gerichte, soweit die Zivilprozessordnung nichts anderes bestimmt. Letzteres ist für Streitigkeiten aus Mietvertrag nicht der Fall, sodass das kantonale Recht, in casu das Recht des Kantons Zürich, massgebend ist.
Nach § 21 Abs. 1 lit. a des Zürcherischen Gesetzes über die Gerichts- und Behördenorganisation im Zivil- und Strafprozess vom 10. Mai 2010 (GOG-ZH; LS 211.1) entscheidet das Mietgericht erstinstanzlich "Streitigkeiten aus Miet- (<ref-law>) und aus Pachtverhältnissen (<ref-law>) für Wohn- und Geschäftsräume". § 26 GOG-ZH regelt die Zuständigkeit des Einzelrichters und des Kollegialgerichts des Mietgerichts.
Das Mietgericht ist demnach nicht für alle Mietstreitigkeiten zuständig, sondern nur für solche, die sich auf Wohn- und Geschäftsräume im Sinne von <ref-law> beziehen (vgl. Urteil des Obergerichts des Kantons Zürich vom 30. Mai 2017, ZR 116 [2017], Nr. 54).
3.2. In casu entscheidet sich die sachliche Zuständigkeit des vom Beschwerdeführer angerufenen Mietgerichts danach, ob die Miete des Spritzenhäuschens als Geschäftsraummiete gilt oder nicht (eine Wohnnutzung fällt dafür von vornherein ausser Betracht).
Diese Frage ist einzig für die Bestimmung der (sachlichen) Zuständigkeit relevant, indessen nicht für die Entscheidung des Streits in materieller Hinsicht. Der Beschwerdeführer macht Schadenersatz wegen einem Mangel der Mietsache (feuchte Wände) gestützt auf <ref-law> geltend. Diese Bestimmung findet auf alle Mietsachen Anwendung, nicht nur auf Wohn- und Geschäftsräume im Sinne von <ref-law>. In der Sache spielt die Frage, ob es sich bei der Miete des Spritzenhäuschens um eine Geschäftsraummiete handelt, mithin keine Rolle.
Dementsprechend bilden die Tatsachen, aufgrund derer die Entscheidung dieser Frage vorzunehmen ist, einfachrelevante Tatsachen, da sie lediglich für die (sachliche) Zuständigkeit massgebend sind. Diese Tatsachen müssen im Stadium der Zuständigkeitsprüfung vom Kläger bewiesen werden, sofern der Beklagte - wie in casu - die Unzuständigkeitseinrede erhebt und die Vorbringen des Klägers bestreitet (<ref-ruling> E. 5.1; Urteil 4A_619/2020 vom 17. Februar 2021 E. 2.1.1, zur Publikation bestimmt).
Entgegen der Rüge des Beschwerdeführers hat die Vorinstanz mithin zu Recht nicht die Theorie der doppelrelevanten Tatsachen zur Anwendung gebracht. Ein bloss schlüssiger Tatsachenvortrag, wie er bei Vorliegen doppelrelevanter Tatsachen im Eintretensstadium genügt hätte, war mithin in casu nicht ausreichend. Vielmehr hat die Vorinstanz dem Beschwerdeführer zutreffend den Beweis für die einfachrelevanten Tatsachen auferlegt, aufgrund derer auf eine Geschäftsraummiete im Sinne von <ref-law> geschlossen werden könnte.
4.
4.1. Nach der Bestimmung von § 21 Abs. 1 lit. a GOG-ZH entscheidet das Mietgericht über Mietstreitigkeiten, die sich auf Wohn- und Geschäftsräume im Sinne von <ref-law> beziehen (Erwägung 3.1) Das kantonalzürcherische Recht verweist damit für die Zuständigkeit des Mietgerichts auf eine materiellrechtliche Bestimmung des Bundesrechts bzw. es stellt auf bundeszivilrechtliche Begrifflichkeiten ab. In einem solchen Fall wird das für anwendbar erklärte Bundesrecht bzw. der verwendete Begriff als kantonale Regelung behandelt (Urteile 4A_165/2014 vom 21. Juli 2014 E. 4.1; 4A_375/2008 vom 18. November 2008 E. 2.1; je mit Hinweisen). Ob es sich in der vorliegenden Streitigkeit um eine solche über eine Geschäftsraummiete handelt, ist damit einzig eine Frage des kantonalen Rechts.
Dessen Anwendung prüft das Bundesgericht - von hier nicht zutreffenden Ausnahmen (Art. 95 lit. c-e BGG) abgesehen - nur auf die Verletzung verfassungsmässiger Rechte, namentlich auf Willkür hin, wenn und soweit entsprechende Rügen erhoben und begründet werden (<ref-law>; <ref-ruling> E. 2.3; <ref-ruling> E. 2.3).
4.2. Nach <ref-law> gelten die Bestimmungen über die Miete von Wohn- und Geschäftsräumen auch für Sachen, die der Vermieter zusammen mit diesen Räumen dem Mieter zum Gebrauch überlässt.
Die Zuständigkeit des Mietgerichts hängt mithin davon ab, ob es sich beim Spritzenhäuschen um einen Geschäftsraum bzw. ein Nebenobjekt zu einem solchen handelt oder nicht.
Zur Beurteilung dieser Frage hat die Vorinstanz eine eingehende Würdigung der Vorbringen und Beweise vorgenommen und auch begründet, weshalb sie in antizipierter Beweiswürdigung oder mangels Entscheidrelevanz auf gewisse Zeugenbefragungen verzichtete. Der Beschwerdeführer hatte behauptet, er benutze das Spritzenhäuschen als Warenlager des Handels mit Oldtimer-Ersatzteilen. Die Vorinstanz kam jedoch zum Schluss, aufgrund der Behauptungen des Mieters und der dazu eingereichten Belege sei nicht hinreichend dargetan, dass im Büro am U._weg ein geschäftlicher Ersatzteilhandel betrieben worden sei, zu welchem das Spritzenhäuschen als Lager diente. Es sei mithin kein Nebenobjekt eines Geschäftsraums am U._weg. Umso weniger sei das Spritzenhäuschen selber ein Geschäftsraum im Sinne von <ref-law>; der Mieter habe nicht beweisen können, dass die Parteien den Gebrauch des Spritzenhäuschens zu Geschäftszwecken vereinbart hätten, auch nicht konkludent.
4.3. Der Beschwerdeführer vermöchte diese Beweiswürdigung vor Bundesgericht nur umzustossen, wenn er sie als willkürlich ausweisen würde (Erwägung 2.3). Dies tut er aber nicht. Stattdessen trägt er seitenweise appellatorische Kritik vor und erweitert den Sachverhalt, ohne hinreichende Sachverhaltsrügen vorzutragen (vgl. Erwägung 2.2). Willkür wird nicht aufgezeigt, indem einmal mehr der eigene Standpunkt ausgebreitet und erst noch teilweise auf neue Behauptungen gestützt wird. Darauf ist nicht einzutreten. Ohnehin fussen die Darlegungen des Beschwerdeführers auf der irrigen Annahme, er müsse die zuständigkeitsdeterminierenden Tatsachen bloss schlüssig vortragen. Wie ausgeführt (Erwägung 3.2), sind diese Tatsachen vorliegend einfachrelevant und daher zu beweisen. Dies ist dem Beschwerdeführer gemäss Vorinstanz nicht gelungen. Dabei bleibt es, nachdem der Beschwerdeführer die vorinstanzliche Beweiswürdigung nicht als willkürlich ausgewiesen hat.
4.4. Somit ist von der vorinstanzlichen Feststellung auszugehen, dass nicht erwiesen ist, dass im Büro am U._weg (Hauptsache) ein geschäftlicher Ersatzteilhandel betrieben wurde. Eine Qualifikation des Spritzenhäuschens als Nebensache eines Geschäftsraums im Sinne von <ref-law> entfällt damit von vornherein, ohne dass näher geprüft werden müsste, ob ein hinreichender funktioneller Zusammenhang zur Hauptsache besteht (vgl. dazu <ref-ruling> E. 2.1; <ref-ruling> E. 2a; Urteil 4A_186/2017 vom 4. Dezember 2017 E. 4.1).
4.5. Aufgrund der verbindlichen Feststellungen der Vorinstanz scheidet auch eine Qualifikation des Spritzenhäuschens selber als Geschäftsraum im Sinne von <ref-law> aus. Nach der Beschwerdegegnerin wurde das Spritzenhäuschen zum Einstellen von zwei Oldtimer-Fahrzeugen gemietet. Der Beschwerdeführer vermochte seine anderslautende Behauptung nicht darzutun. Die Vorinstanz stellte fest, er habe nicht bewiesen, dass die Nutzung als Ersatzteillager vereinbart worden sei. Auf der Grundlage dieser Feststellung könnte das Spritzenhäuschen selbst dann nicht als Geschäftsraum qualifiziert werden, wenn man die sehr weite Auslegung von <ref-ruling> zugrunde legte. In diesem Urteil werden als Geschäftsräume all jene Räumlichkeiten betrachtet, die tatsächlich dazu beitragen, dass der Mieter seine Persönlichkeit in privater oder wirtschaftlicher Hinsicht entfalten kann (<ref-ruling> E. 4b). In späteren Entscheiden wurde diese sehr weit gefasste Formulierung unter Hinweis auf die Kritik in der Lehre nicht wieder aufgenommen (Urteil 4C.425/1994 vom 6. Februar 1995 E. 2a; zusammengefasst in: Peter Münch, Mieterstreckung: Hobby-Pferdestall als Geschäftsraum?, ZBJV 131 [1995], S. 418 f.).
Gemäss Rechtsprechung gilt namentlich eine zum Abstellen von Autos separat gemietete Garage nicht als Geschäftsraum (BGE <ref-ruling> E. 2 S. 233 mit Hinweisen). Nichts anderes gilt vorliegend: Das separat gemietete Spritzenhäuschen wurde gemäss der nicht als willkürlich ausgewiesenen Beweiswürdigung der Vorinstanz zum Einstellen von zwei Oldtimer-Fahrzeugen gemietet und ist daher nicht als Geschäftsraum im Sinne von § 21 Abs. 1 lit. a GOG-ZH i.V.m. <ref-law> zu qualifizieren.
4.6. Damit erkannte die Vorinstanz zu Recht, dass die vorliegende Klage nicht in den sachlichen Zuständigkeitsbereich des Mietgerichts nach § 21 Abs. 1 lit. a GOG-ZH fällt und darauf nicht einzutreten ist.
5.
Das Urteil des Obergerichts ist demnach nicht zu beanstanden. Entsprechend besteht kein Anlass, die obergerichtliche Kosten- und Entschädigungsregelung neu zu bestimmen, da diese vom Beschwerdeführer nicht unabhängig vom Verfahrensausgang angefochten wird.
6.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'500.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 3. Mai 2021
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Brugger