Citation: 4A_17/2017 E. A

A.a. Die C.________ AG (Vermieterin, Beklagte, Beschwerdegegnerin) erwarb am 6. Dezember 2001 die aneinander grenzenden Liegenschaften Strasse X.________ und Strasse Y.________ in Zürich. Der Kaufpreis betrug Fr. 21'529'000.--. Im Jahre 2012 baute die Vermieterin die beiden Liegenschaften um, wofür sie der Generalunternehmerin Fr. 7'007'960.-- bezahlte; für Zusatzarbeiten leistete sie überdies noch Fr. 896'372.--. Nach dem Umbau wiesen die beiden Liegenschaften insgesamt 4'027 m2 Laden-, Restaurations-, Büro-, Lager-, Werkstatt- und Wohnräume auf. Unter anderem sind im Dachstock der beiden Liegenschaften insgesamt sechs 3.5-Zimmer-Maisonettewohnungen neu eingebaut worden. Am 20. März 2013 schlossen A.________ (Mieter 1, Kläger 1, Beschwerdeführer 1) und B.________ (Mieter 2, Kläger 2, Beschwerdeführer 2) mit der Vermieterin einen Vertrag über die Miete einer der 3.5-Zimmer-Maisonettewohnungen im Dachstock der Liegenschaft Strasse X.________ in Zürich. Der Mietzins wurde auf Fr. 3'900.-- zuzüglich Fr. 300.-- Nebenkosten à conto pro Monat festgesetzt. Die Mieter verpflichteten sich überdies, eine Sicherheit von Fr. 12'600.-- zu leisten. Als Mietbeginn wurde der 1. April 2013 festgelegt. A.b. Am 26. August 2013 reichten die Mieter beim Mietgericht Zürich Klage ein mit dem - schliesslich massgebenden - Begehren, es sei der Anfangsmietzins für die 3.5-Zimmer-Maisonettewohnung als missbräuchlich zu erklären, soweit er monatlich netto Fr. 2'200.-- übersteigt. Die bei der Swiss Caution hinterlegte Mietzinsgarantie von Fr. 12'600.-- sei auf Fr. 6'600.-- zu reduzieren. Das Mietgericht Zürich wies die Klage mit Urteil vom 16. Juni 2015 ab, im Wesentlichen in der Erwägung, eine Aufteilung der pauschalen Anlagekosten auf die einzelnen Mietobjekte wäre entgegen der Ansicht der Beklagten zwar möglich, aber nur mit einem Gutachten, dessen Kosten die beweisbelasteten Kläger nicht vorgeschossen hätten. Die vorliegenden Unterlagen genügten zum den Klägern obliegenden Beweis der Missbräuchlichkeit nicht. A.c. Das Obergericht des Kantons Zürich wies die dagegen von den Klägern eingereichte Berufung am 9. November 2015 mit der Begründung ab, die Kläger seien gar nicht zur Anfechtung des Anfangsmietzinses berechtigt. Diesen Entscheid hob das Bundesgericht mit Urteil vom 18. Mai 2016 (BGE 142 III 442) auf und wies die Sache an die Vorinstanz zurück.