Sachverhalt: A. X._ (Beschwerdeführer) reichte am 4. Juli 2012 beim Handelsgericht des Kantons Zürich Klage ein mit dem Antrag, die Y._ AG (Beschwerdegegnerin) sei zu verpflichten, ihm EUR 1'212'100.-- nebst Zins zu 5% seit dem 1. März 2000 "sofort zu bezahlen". Mit Verfügung vom 6. Juli 2012 wurde die Klage der Beschwerdegegnerin zugestellt und dem Beschwerdeführer Frist angesetzt zur Leistung eines Gerichtskostenvorschusses von Fr. 46'000.--. Das daraufhin gestellte Gesuch des Beschwerdeführers um Gewährung der unentgeltlichen Rechtspflege wurde mit Beschluss vom 18. Dezember 2012 abgewiesen. Gleichzeitig wurde dem Beschwerdeführer nochmals Frist zur Leistung des Gerichtskostenvorschusses angesetzt. Am 11. Februar 2013 wurde eine weitere Fristerstreckung abgelehnt, jedoch dem Beschwerdeführer eine Nachfrist gewährt unter Androhung, dass bei Säumnis auf die Klage nicht eingetreten werde. Der Beschwerdeführer liess auch die Nachfrist ungenutzt verstreichen und leistete den Kostenvorschuss nicht. Demzufolge trat das Handelsgericht mit Beschluss vom 18. März 2013 auf die Klage nicht ein. Es setzte die Gerichtsgebühr auf Fr. 12'000.-- fest (Dispositiv-Ziffer 2) und auferlegte die Kosten dem Beschwerdeführer (Dispositiv-Ziffer 3). Ferner verpflichtete es den Beschwerdeführer, der Beschwerdegegnerin eine Parteientschädigung von Fr. 9'000.-- zu bezahlen (Dispositiv-Ziffer 4). B. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, den Beschluss des Handelsgerichts vom 18. März 2013 dahingehend zu ändern, dass keine Gerichtsgebühren zulasten des Beschwerdeführers erhoben werden und der Beschwerdegegnerin keine Parteientschädigung zugesprochen wird. Eventualiter seien die Gerichtskosten auf einen symbolischen Betrag, höchstens aber auf Fr. 500.-- festzusetzen. Subeventualiter sei der Beschluss aufzuheben und die Sache zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin und die Vorinstanz verzichteten auf eine Vernehmlassung. 