Sachverhalt: A. A.a. X._ (Kläger 1, Beschwerdeführer 1) war ab 16. März 2007 Gesellschafter und Geschäftsführer mit Einzelunterschrift der A._ GmbH mit Sitz an der Strasse B._ in Zürich. Y._ (Klägerin 2, Beschwerdeführerin 2) war ab gleichem Datum Geschäftsführerin mit Einzelunterschrift dieser Gesellschaft. Diese betrieb an der Strasse C._ in Zürich das Restaurant D._. Die Kläger sind Lebenspartner und haben einen gemeinsamen Sohn. A.b. Am frühen Morgen des 19. Oktober 2007 brach im Restaurant D._ ein Brand aus. In diesem Zusammenhang wurde E._, der Bruder der Klägerin 2, vom Obergericht des Kantons Zürich durch Urteil vom 12. April 2011 wegen Brandstiftung verurteilt. Eine dagegen erhobene Beschwerde wurde mit dem Urteil des Bundesgerichts 6B_452/2011 vom 23. September 2011 abgewiesen. Auch gegen die beiden Kläger wurde ein Strafverfahren eröffnet. Dieses wurde am 26. Februar 2009 eingestellt. A.c. Am 20. November 2008 wurde über die A._ GmbH der Konkurs eröffnet. In diesem Konkurs wurde eine Forderung des Klägers 1 von Fr. 320'699.60 und eine solche der Klägerin 2 von Fr. 141'641.-- je in der 3. Klasse kolloziert. Ferner wurde eine Forderung eines zweiten Sohnes der Klägerin 2, F._, im Betrag von Fr. 77'600.-- ebenfalls in der 3. Klasse kolloziert. Letztere Forderung hat sich die Klägerin 2 von ihrem Sohn abtreten lassen. A.d. Mit Abtretungsverfügungen vom 31. Mai 2010 trat das Konkursamt Höngg-Zürich gestützt auf Art. 260 SchKG die Forderungen der Masse gegen die Versicherung Z._ AG (Beklagte, Beschwerdegegnerin) aus dem Brandschadenfall vom 19. Oktober 2007 an die beiden Kläger sowie an fünf weitere Personen ab. B. B.a. Mit Klagen vom 5. bzw. 6. Dezember 2012 beantragten die Kläger als Abtretungsgläubiger dem Handelsgericht des Kantons Zürich, die Beklagte sei zu verpflichten, ihnen bzw. der Konkursmasse A._ GmbH einen Betrag von Fr. 450'000.-- (bzw. Fr. 449'669.80) nebst Zins unter Vorbehalt des Nachklagerechts zu bezahlen. B.b. Mit Beschluss vom 18. Dezember 2012 wies das Handelsgericht ein erstes Gesuch der Kläger um unentgeltliche Prozessführung ab, weil nicht nachgewiesen sei, dass G._, ein weiterer Abtretungsgläubiger, auf die Verfolgung der Ansprüche verzichtet habe. Nachdem die Kläger letzteres nachgewiesen hatten, prüfte das Handelsgericht die Gesuche um unentgeltliche Prozessführung erneut und wies sie mit Beschluss vom 15. Mai 2013 wegen Aussichtslosigkeit ab. C. Mit Beschwerden in Zivilsachen beantragen die Kläger dem Bundesgericht, der Beschluss des Handelsgerichts vom 15. Mai 2013 sei aufzuheben und die unentgeltliche Rechtspflege zu gewähren; eventuell sei die Sache zur Neubeurteilung an das Handelsgericht zurückzuweisen. Gleichzeitig stellen sie auch für das Verfahren vor Bundesgericht ein Gesuch um unentgeltliche Prozessführung. Ausserdem beantragen sie, der Beschwerde sei aufschiebende Wirkung zu erteilen. Aufgefordert, zum Gesuch um aufschiebende Wirkung Stellung zu nehmen, beantragt die Beschwerdegegnerin dessen Abweisung. Das Handelsgericht hat auf eine Stellungnahme verzichtet. Es wurden keine Vernehmlassungen in der Sache eingeholt.