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.

Erwägungen:
1.
Das Verfahren wird in einer der Amtssprachen (Deutsch, Französisch, Italienisch, Rumantsch Grischun) geführt, in der Regel in der Sprache des angefochtenen Entscheids. Verwenden die Parteien eine andere Amtssprache, so kann das Verfahren in dieser Sprache geführt werden (<ref-law>). Vorliegend erging der angefochtene Beschluss auf Deutsch. Der Beschwerdeführer bedient sich der französischen, die Beschwerdegegnerin der deutschen Sprache. Bei dieser Sachlage ergeht das Urteil des Bundesgerichts in der Sprache des angefochtenen Entscheids.
2.
Gegen Entscheide der als einzige kantonale Instanzen im Sinne von <ref-law> zuständigen Handelsgerichte ist die Beschwerde an das Bundesgericht gemäss <ref-law> streitwertunabhängig gegeben (<ref-ruling> E. 1.2). Damit erweist sich die vorliegende, einzig gegen den Kostenentscheid (Auferlegung von Kosten und Parteientschädigung) gerichtete Beschwerde ohne weiteres als zulässig. Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
3.
Der Beschwerdeführer beanstandet zunächst die Auferlegung der Gerichtskosten in der Höhe von Fr. 12'000.--.
3.1. Er ist der Auffassung, für das Nichteintreten wegen Nichtleistung des Kostenvorschusses dürften überhaupt keine Kosten erhoben werden.
Diese Ansicht entbehrt der Grundlage. Die fristgemässe Leistung des Kostenvorschusses bildet eine Prozessvoraussetzung (<ref-law>). Säumnis zieht Nichteintreten nach sich (<ref-law>). Für derartige Nichteintretensentscheide sieht das Bundesrecht keine Kostenfreiheit vor. Im Kanton Zürich besteht ebenso wenig eine Kostenbefreiung nach kantonalem Recht (<ref-law>). Indem <ref-law> bestimmt, dass bei Nichteintreten die klagende Partei als unterliegend gilt, bringt der Bundesgesetzgeber zudem zum Ausdruck, dass auch für Nichteintretensentscheide Kosten erhoben werden können. Es ist mithin zulässig, das Nichteintreten auf eine Klage mangels (fristgemässer) Leistung des Kostenvorschusses mit Kosten zu verbinden (ebenso Richard Kuster, in: Baker & McKenzie [Hrsg.], Schweizerische Zivilprozessordnung, Bern 2010, N. 6 zu <ref-law>; Staehelin/Staehelin/Grolimund, Zivilprozessrecht, 2. Aufl. 2013, § 16 Rz. 29; Suter/von Holzen, in: Sutter-Somm/Hasenböhler/Leuenberger [Hrsg.], Kommentar zur Schweizerischen Zivilprozessordnung, 2. Aufl. 2013, N. 15 zu <ref-law>; Denis Tappy, in: Bohnet und andere [Hrsg.], Code de procédure civile commenté, 2011, N. 38 zu <ref-law>).
Im Übrigen erhebt auch das Bundesgericht im Grundsatz eine Gebühr, wenn es zufolge Nichtleistung des Kostenvorschusses auf eine Beschwerde nicht eintritt (vgl. Thomas Geiser, in: Basler Kommentar, Bundesgerichtsgesetz, 2. Aufl. 2011, N. 37 zu <ref-law>). Die gegenteilige Behauptung des Beschwerdeführers trifft nicht zu.
3.2. Eventualiter richtet sich der Beschwerdeführer gegen die Höhe der vorinstanzlich festgesetzten Gerichtsgebühr von Fr. 12'000.--.
3.2.1. Nach <ref-law> setzen die Kantone die Tarife für die Prozesskosten fest. Im Kanton Zürich gelangt die gestützt auf § 199 Abs. 1 des Gesetzes des Kantons Zürich vom 10. Mai 2010 über die Gerichts- und Behördenorganisation im Zivil- und Strafprozess (GOG) erlassene Gebührenverordnung des Obergerichts vom 8. September 2010 (GebV OG) zur Anwendung. § 2 Abs. 1 GebV OG nennt als Grundlage für die Festsetzung der Gebühren im Zivilprozess den Streitwert bzw. das tatsächliche Streitinteresse, den Zeitaufwand des Gerichts und die Schwierigkeit des Falls (vgl. auch § 199 Abs. 3 GOG). § 4 GebV OG sieht für vermögensrechtliche Streitigkeiten ein nach Streitwert abgestuftes Raster für die Grundgebühr vor. Bei einem Streitwert über Fr. 1 Mio. bis Fr. 10 Mio. beträgt die Grundgebühr Fr. 30'750.-- zuzüglich 1% des Fr. 1 Mio. übersteigenden Streitwertes. Die Grundgebühr kann unter Berücksichtigung des Zeitaufwandes des Gerichts und der Schwierigkeit des Falls ermässigt oder um bis zu einem Drittel, in Ausnahmefällen bis auf das Doppelte, erhöht werden (§ 4 Abs. 2 GebV OG). Wird das Verfahren ohne Anspruchsprüfung oder nach Säumnis erledigt, kann die gemäss §§ 4-8 bestimmte Gebühr bis auf die Hälfte reduziert werden (§ 10 Abs. 1 GebV OG).
Für die vorliegende Klage mit einem Streitwert von Fr. 1,5 Mio. setzte die Vorinstanz die Grundgebühr in Übereinstimmung mit § 4 Abs. 1 GebV OG auf Fr. 35'750.-- fest. In Anwendung von § 4 Abs. 2 und § 10 Abs. 1 GebV OG reduzierte sie die ordentliche Grundgebühr auf rund einen Drittel, mithin auf Fr. 12'000.--.
Der Beschwerdeführer rügt, die vorinstanzliche Kostenfestsetzung verletze das Kostendeckungs- sowie das Äquivalenzprinzip und sei überdies willkürlich. Zudem habe die Vorinstanz <ref-law> missachtet.
3.2.2. Dass die Vorinstanz die Gerichtsgebühr auch zur Abgeltung des Aufwands für die Behandlung des Gesuchs um unentgeltliche Rechtspflege festgelegt hätte, geht aus dem angefochtenen Beschluss nicht hervor und ist entgegen der Auffassung des Beschwerdeführers nicht anzunehmen, nachdem die Vorinstanz im Beschluss vom 18. Dezember 2012 (E. 7) betreffend Abweisung des Gesuchs um unentgeltliche Rechtspflege ausdrücklich auf das Verbot der Kostenerhebung im Gesuchsverfahren hinwies. Mithin kann der Vorinstanz insofern kein fehlerhaftes Vorgehen vorgeworfen werden.
3.2.3. Das Kostendeckungsprinzip besagt, dass der Gebührenertrag die gesamten Kosten des betreffenden Verwaltungszweigs nicht oder nur geringfügig übersteigen soll (vgl. <ref-ruling> E. 3a/aa mit Hinweisen). Es spielt im Allgemeinen für Gerichtsgebühren keine Rolle, decken doch erfahrungsgemäss die von den Gerichten eingenommenen Gebühren die entsprechenden Kosten bei Weitem nicht (<ref-ruling> E. 3 mit Hinweisen). Der Beschwerdeführer zeigt jedenfalls nicht auf, dass Letzteres für die Zürcher Justiz nicht zutreffen soll. Seine Ansicht, das Kostendeckungsprinzip sei verletzt, begründet er vielmehr mit dem unbehelflichen Hinweis, dass die vom Gericht vorgenommenen Handlungen konkret weniger gekostet hätten als die in Rechnung gestellte Gerichtsgebühr. Die Rüge erweist sich als unbegründet (vgl. Urteile 2C_404/2010 vom 20. Februar 2012 E. 6.5; 4P.315/2006 vom 22. Mai 2007 E. 2.2.2).
3.2.4. Das Äquivalenzprinzip verlangt in Konkretisierung des Verhältnismässigkeitsgrundsatzes insbesondere, dass eine Gebühr nicht in einem offensichtlichen Missverhältnis zum objektiven Wert der bezogenen Leistung stehen darf und sich in vernünftigen Grenzen bewegen muss (im Allgemeinen: <ref-ruling> E. 4.1; <ref-ruling> E. 2.3 S. 228; <ref-ruling> E. 3a/bb; je mit Hinweisen; im Speziellen für Gerichtsgebühren: <ref-ruling> E. 2a mit Hinweisen). Der Wert der Leistung bemisst sich nach dem wirtschaftlichen Nutzen, den sie dem Pflichtigen bringt, oder nach dem Kostenaufwand der konkreten Inanspruchnahme im Verhältnis zum gesamten Aufwand des betreffenden Verwaltungszweigs, wobei schematische, auf Wahrscheinlichkeit und Durchschnittserfahrungen beruhende Massstäbe angelegt werden dürfen. Es ist nicht notwendig, dass die Gebühren in jedem Fall genau dem Verwaltungsaufwand entsprechen; sie sollen indessen nach sachlich vertretbaren Kriterien bemessen sein und nicht Unterscheidungen treffen, für die keine vernünftigen Gründe ersichtlich sind (<ref-ruling> E. 4a S. 52; <ref-ruling> E. 3a/bb). Bei der Festsetzung von Verwaltungsgebühren darf deshalb innerhalb eines gewissen Rahmens auch der wirtschaftlichen Situation des Pflichtigen und dessen Interesse am abzugeltenden Akt Rechnung getragen werden, und bei Gerichtsgebühren darf namentlich der Streitwert eine massgebende Rolle spielen. Dem Gemeinwesen ist es nicht verwehrt, mit den Gebühren für bedeutende Geschäfte den Ausfall in weniger bedeutsamen Fällen auszugleichen. In Fällen mit hohem Streitwert und starrem Tarif, der die Berücksichtigung des Aufwandes nicht erlaubt, kann die Belastung allerdings unverhältnismässig werden, namentlich dann, wenn die Gebühr in Prozenten oder Promillen festgelegt wird und eine obere Begrenzung fehlt (BGE <ref-ruling> E. 2.3 mit Hinweisen).
Der Zürcher Tarif zieht als Grundlage für die Bemessung der Gerichtsgebühr nicht allein den Streitwert bzw. das tatsächliche Streitinteresse heran, sondern berücksichtigt auch den Zeitaufwand des Gerichts und die Schwierigkeit des Falls. § 4 Abs. 2 GebV OG erlaubt eine Ermässigung der Grundgebühr unter Berücksichtigung dieser Kriterien ohne Begrenzung nach unten. Sodann kann die - allenfalls bereits ermässigte - Grundgebühr bei Erledigung ohne Anspruchsprüfung oder nach Säumnis bis auf die Hälfte reduziert werden (§ 10 Abs. 1 GebV OG). Mit diesen Möglichkeiten kann sowohl dem Nutzen für den Gebührenpflichtigen als auch dem Aufwandkriterium hinreichend Rechnung getragen werden. Sie erlauben, die Gerichtsgebühr so festzusetzen, dass sie sich in vernünftigen Grenzen hält und nicht in einem offensichtlichen Missverhältnis zum objektiven Wert der bezogenen Leistung steht (vgl. Urteil 4P.315/2006 vom 22. Mai 2007 E. 2.2.2). Die anwendbaren Tarifbestimmungen sind demnach unter dem Gesichtspunkt des Äquivalenzprinzips nicht zu beanstanden.
Damit stellt sich nur die Frage, ob dem Äquivalenzprinzip im konkreten Einzelfall nachgelebt wurde. Der Beschwerdeführer bringt vor, der Nichteintretensbeschluss habe der Vorinstanz den denkbar geringsten Aufwand verursacht, zumal der Aufwand für die Behandlung des Gesuchs um unentgeltliche Rechtspflege mit Blick auf die dafür vorgeschriebene Kostenlosigkeit nicht berücksichtigt werden dürfe (dazu Erwägung 3.2.2).
Wenn eine Gebühr von Fr. 12'000.-- für einen mangels Leistung des Kostenvorschusses gefällten Nichteintretensentscheid gemessen am Aufwand als sehr hoch erscheinen mag, so ist andererseits zu berücksichtigen, dass der Streitwert auch bei Nichteintretensentscheiden ein relevantes Bemessungskriterium bilden darf. Der Beschwerdeführer wendet ein, der angefochtene Beschluss habe keine materielle Rechtskraftwirkung in Bezug auf den eingeklagten Anspruch. Die Leistung der Vorinstanz sei daher für den Beschwerdeführer (wie auch für die Beschwerdegegnerin) ohne jeglichen Nutzen. Diese Argumentation verfängt nicht. Der objektive Wert der bezogenen Leistung kann nicht nach der Art der Verfahrenserledigung respektive dem effektiven Prozessausgang in Bezug auf das eingeklagte Recht bestimmt werden. Der wirtschaftliche Nutzen für den Rechtssuchenden besteht vielmehr im Zugang zur Justiz an sich, der darin besteht, dass er die Möglichkeit hat, seinen Anspruch mittels einer zulässigen Klage gerichtlich durchzusetzen. Der Wert dieser Möglichkeit ist umso grösser, je höher der Betrag des Klageanspruchs (Streitwert) liegt.
In Berücksichtigung aller massgebenden Kriterien ist daher fraglich, ob die erhobene Gerichtsgebühr unter dem Aspekt des Äquivalenzprinzips als unverhältnismässig beurteilt werden muss. Wie sich aus der nachfolgenden Erwägung ergibt, braucht die Frage indessen nicht abschliessend beantwortet zu werden.
3.2.5. Der Beschwerdeführer moniert, dass die Vorinstanz in Willkür verfallen sei, indem sie von der nach unten offenen Ermässigungsmöglichkeit gemäss § 4 Abs. 2 GebV OG völlig unzureichend Gebrauch gemacht habe.
Nach ständiger Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, 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. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 2.4 mit Hinweisen). Dabei greift das Bundesgericht in Ermessensentscheide, zu denen Entscheide über die Höhe der Gerichtsgebühr gehören, nur mit grösster Zurückhaltung ein (Urteil 4A_680/2011 vom 2. Dezember 2011 E. 2).
Da die Vorinstanz die ordentliche Gerichtsgebühr pauschal in Anwendung von § 4 Abs. 2 und § 10 Abs. 1 GebV OG auf rund einen Drittel reduzierte, ist nicht klar, in welchem betragsmässigen Umfang sie nach § 4 Abs. 2 GebV OG dem geringen Zeitaufwand durch eine Ermässigung der ordentlichen Gerichtsgebühr Rechnung trug und inwieweit sie von der Kürzungsmöglichkeit nach § 10 Abs. 1 GebV OG Gebrauch machte. Die Kürzungsmöglichkeit nach § 10 Abs. 1 GebV OG ("Besonderheiten bei der Verfahrenserledigung") trägt dem Umstand Rechnung, dass die Erledigung ohne Anspruchsprüfung oder bei Säumnis oftmals mit geringerem Aufwand verbunden ist, als wenn eine materielle Anspruchsprüfung erfolgt. Dies braucht indessen nicht stets der Fall zu sein. So kann beispielsweise das Nichteintreten zufolge internationaler oder örtlicher Unzuständigkeit mit erheblichem Aufwand verbunden sein. § 10 Abs. 1 GebV OG ist aus diesem Grund als Kann-Vorschrift formuliert und eröffnet einen Rahmen (bis zur Hälfte) (vgl. Hauser/Schweri/Lieber, Kommentar zum zürcherischen Gesetz über die Gerichts- und Behördenorganisation im Zivil- und Strafprozess, 2012, N. 38 zu § 199 GOG).
Das Nichteintreten mangels Leistung des Kostenvorschusses verursacht demgegenüber in der Tat einen denkbar geringen Aufwand für das Gericht, weshalb hier eine Ermässigung gemäss § 4 Abs. 2 GebV OG und kumulativ die Ausschöpfung der Kürzungsmöglichkeit um die Hälfte nach § 10 Abs. 1 GebV OG zwingend erscheint. Davon ist im vorliegenden Fall auszugehen, nachdem die Vorinstanz die ordentliche Gerichtsgebühr insgesamt auf rund einen Drittel kürzte: Der geringe Aufwand für das Gericht führte zu einer maximalen Kürzung nach § 10 Abs. 1 GebV OG, und die Vorinstanz berücksichtigte den nämlichen Umstand zudem durch eine Ermässigung der Grundgebühr nach § 4 Abs. 2 GebV OG.
Der Beschwerdeführer hält die Reduktion der ordentlichen Gerichtsgebühr auf rund einen Drittel für ungenügend. Er argumentiert, indem die GebV OG für die Ermässigung keinerlei Begrenzung nach unten festlege, komme zum Ausdruck, dass bei einem - wie hier - denkbar geringsten Zeitaufwand des Gerichts die Gerichtsgebühr auf Null oder auf einen symbolischen Betrag zu reduzieren sei. Andere Kantone würden denn auch für Nichteintretensentscheide wegen Nichtleistung des Kostenvorschusses keine (Waadt) oder sehr geringe Gebühren (Genf) vorsehen. Es sei stossend und laufe dem Gerechtigkeitsgedanken zuwider, dass der Beschwerdeführer, nur weil er seine Klage im Kanton Zürich habe anhängig machen müssen, mit einer Gebühr in der Höhe von Fr. 12'000.-- konfrontiert sei, während er in anderen Kantonen für die gleiche Leistung nichts oder fast nichts hätte bezahlen müssen, zumal auch in Zürich eine ausdrückliche gesetzliche Grundlage für eine Reduktion der Gerichtsgebühr bei geringem Zeitaufwand (ohne Begrenzung nach unten) bestehe. Die Belastung mit Kosten von Fr. 12'000.-- sei auch im Ergebnis unhaltbar, nachdem der Beschwerdeführer mangels hinreichender Mittel um unentgeltliche Rechtspflege habe ersuchen und - nach Abweisung des Gesuchs - auf seine Klage verzichten müssen, weil er den Kostenvorschuss nicht habe aufbringen können.
Der Willkürvorwurf ist berechtigt. § 4 Abs. 2 GebV OG sieht vor, dass die Grundgebühr unter Berücksichtigung des Zeitaufwands des Gerichts und der Schwierigkeit des Falls ermässigt werden kann, und legt dafür keine Begrenzung nach unten fest (vgl. zur Berücksichtigung von Zeitaufwand und Schwierigkeit des Falls allgemein Hauser/Schweri/Lieber, a.a.O., N. 8 sowie 20 f. zu § 199 GOG). Vorliegend kommt es einer unsachgemässen Nichtausschöpfung des dem Gericht eingeräumten Ermessensspielraums gleich, wenn die Vorinstanz dem Umstand, dass der Fall für das Gericht einen äusserst geringen Zeitaufwand erforderte, nicht durch eine erheblich stärkere Ermässigung der Grundgebühr Rechnung trug. Es ist in der Tat kaum eine andere Konstellation vorstellbar, die dem Gericht noch weniger Aufwand abverlangte, als das Nichteintreten wegen Nichtleistung des Kostenvorschusses. Dabei ist stets im Auge zu behalten, dass der Aufwand für die Behandlung des Gesuchs um unentgeltliche Rechtspflege mit Blick auf <ref-law> - ausser bei Bös- oder Mutwilligkeit, wovon vorliegend aber keine Rede ist - nicht in Rechnung gestellt werden darf (vgl. Erwägung 3.2.2). Die Vorinstanz hat ihr Ermessen unterschritten, indem sie trotz geringstem Zeitaufwand von der Ermässigungsmöglichkeit nach § 4 Abs. 2 GebV OG nur unzureichend Gebrauch machte. Hingegen findet die Ansicht des Beschwerdeführers, es sei unter den gegebenen Umständen gänzlich auf die Erhebung einer Gebühr zu verzichten, im Normtext von § 4 Abs. 2 GebV OG, der nur von "ermässigen" und nicht von "verzichten" spricht, keine Stütze.
Sodann ist dem Beschwerdeführer beizupflichten, dass die erhobene Gebühr von Fr. 12'000.-- im Ergebnis stossend ist, wenn man berücksichtigt, dass der Beschwerdeführer wegen Bedürftigkeit um unentgeltliche Rechtspflege ersuchte und nach deren Ablehnung schliesslich auf die Weiterverfolgung seiner Klage verzichtete. Unter Berücksichtigung dieses Umstands ist die auf Fr. 12'000.-- festgesetzte Gerichtsgebühr schlechterdings nicht mehr vertretbar und willkürlich hoch.
3.3. Die Dispositiv-Ziffer 2 des angefochtenen Beschlusses ist daher aufzuheben. Aus prozessökonomischen Gründen wird darauf verzichtet, die Sache zur Neufestsetzung der Gerichtsgebühr in Berücksichtigung der bundesgerichtlichen Erwägungen an die Vorinstanz zurückzuweisen, zumal diese auf eine Vernehmlassung zur Beschwerde verzichtet und damit ihr Desinteresse an einer Rückweisung und erneuten Ermessensausübung bekundet hat. Das Bundesgericht macht von seiner reformatorischen Kompetenz (<ref-law>) Gebrauch und setzt die Gerichtsgebühr auf Fr. 2'000.-- fest. Dieser Betrag scheint den vorliegenden Umständen angemessen. Er entspricht - in etwa - einer Ermässigung der ordentlichen Grundgebühr von Fr. 35'750.-- um neun Zehntel auf Fr. 3'575.-- nach § 4 Abs. 2 GebV OG und einer Reduktion dieser Gebühr auf die Hälfte, mithin auf Fr. 1'787.50, nach § 10 Abs. 1 GebV OG, aufgerundet auf Fr. 2'000.--.
4.
Der Beschwerdeführer rügt sodann, dass ihm zugunsten der Beschwerdegegnerin eine Parteientschädigung von Fr. 9'000.-- auferlegt wurde.
4.1. Betreffend Parteientschädigung erwog die Vorinstanz, dass sich die Beschwerdegegnerin lediglich zum Gesuch des Beschwerdeführers um Gewährung der unentgeltlichen Rechtspflege habe äussern müssen. Dabei habe sie sich auch zur Aussichtslosigkeit geäussert, was eine entsprechende Instruktion der Rechtsvertreter durch die Klientschaft vorausgesetzt habe. In Anwendung von § 10 Abs. 1 lit. a (betreffend Zwischenentscheide) und § 11 Abs. 4 (erfolgte Instruktion) der (kantonalen) Verordnung des Obergerichts über die Anwaltsgebühren vom 8. September 2010 (AnwGebV) sowie unter Berücksichtigung des hohen Streitwerts setzte sie die Parteientschädigung auf rund einen Viertel der ordentlichen Grundgebühr fest.
4.2. Der Beschwerdeführer beanstandet, die Zusprechung einer Parteientschädigung komme vorliegend einer unzulässigen Entschädigung für die Stellungnahme zum Gesuch um unentgeltliche Rechtspflege gleich.
Da die Vorinstanz die Parteientschädigung einzig mit dem der Beschwerdegegnerin für die Stellungnahme zum Gesuch um unentgeltliche Rechtspflege angefallenen Aufwand rechtfertigte, ist zu prüfen, ob im Gesuchsverfahren um unentgeltliche Rechtspflege der Gegenpartei des Hauptverfahrens eine Parteientschädigung zugesprochen werden darf, wenn sie von der ihr eingeräumten Äusserungsmöglichkeit Gebrauch gemacht hat. Diese Frage ist zu verneinen:
<ref-law> sieht vor, dass die Gegenpartei im Verfahren um Bewilligung der unentgeltlichen Rechtspflege angehört werden kann. Das Gesetz stellt somit die Anhörung der Gegenpartei in das richterliche Ermessen. Der Sinn und Zweck der Anhörung der Gegenpartei besteht darin, dem mit dem Gesuch um Bewilligung der unentgeltlichen Rechtspflege befassten Richter zusätzliche Erkenntnisse zu verschaffen. Denn oft vermag die Gegenpartei zur Abklärung der Vermögens- und Einkommensverhältnisse sowie vor allem der Erfolgsaussichten der gestellten Rechtsbegehren beizutragen (siehe Botschaft vom 28. Juni 2006 zur Schweizerischen Zivilprozessordnung [ZPO], BBl 2006 7303 zu <ref-law>; vgl. auch Alfred Bühler, in: Berner Kommentar, Schweizerische Zivilprozessordnung, 2012, N. 115 f. zu <ref-law>). Nicht geregelt ist, wie es sich mit der Entschädigung der Gegenpartei verhält, wenn sich diese geäussert hat und das Gesuch in der Folge abgewiesen wurde.
Die Frage, ob die Gegenpartei nach einer fakultativen Anhörung gemäss <ref-law> Anspruch auf Parteikostenersatz hat, ist in der Literatur umstritten. Ein Teil der Lehre ist ausdrücklich der Meinung, dass der Gegenpartei diesfalls keine Parteientschädigung zustehe (Bühler, a.a.O., N. 152 zu <ref-law>; Viktor Rüegg, in: Basler Kommentar, Schweizerische Zivilprozessordnung, 2010, N. 9 zu <ref-law>). Andere Autoren schliessen die Zusprechung einer Parteientschädigung in dieser Konstellation dagegen zumindest nicht aus (Frank Emmel, in: Sutter-Somm/Hasenböhler/Leuenberger [Hrsg.], Kommentar zur Schweizerischen Zivilprozessordnung, 2. Aufl. 2013, N. 15 zu <ref-law>; Staehelin/Staehelin/Grolimund, a.a.O., § 16 Rz. 63; Tappy, a.a.O., N. 27 zu <ref-law>). Eine Autorin ist der Auffassung, dass die gesetzliche Grundlage fehle, um die Gegenpartei leer ausgehen zu lassen, soweit diese gemäss Abs. 3 zum Gesuch um unentgeltliche Rechtspflege Stellung genommen und eine Entschädigung verlangt habe (Ingrid Jent-Sørensen, in: Oberhammer [Hrsg.], Kurzkommentar ZPO, 2010, N. 15 zu <ref-law>).
Die Parteientschädigung ist die Vergütung für den Aufwand, den die Beteiligung an einem gerichtlichen Verfahren einer Partei verursacht, namentlich die Kosten einer berufsmässigen Vertretung (vgl. <ref-law>). Allein der Umstand, dass die Gegenpartei des Hauptverfahrens im Gesuchsverfahren um die unentgeltliche Rechtspflege nach <ref-law> bloss fakultativ anzuhören ist, würde es nicht zwingend ausschliessen, ihr eine Parteientschädigung zuzusprechen, wenn sie zur Stellungnahme eingeladen wird und sich vernehmen lässt. Entscheidend ist jedoch, dass der Gegenpartei des Hauptverfahrens im Gesuchsverfahren um unentgeltliche Rechtspflege in diesem Fall keine Parteistellung zukommt (siehe Urteil 5A_29/2013 vom 4. April 2013 E. 1.1 mit Hinweis), da die Bewilligung der unentgeltlichen Rechtspflege das Rechtsverhältnis zwischen dem Gesuchsteller und dem Staat betrifft, nicht aber die Rechte und Pflichten der Gegenpartei tangiert. Dem entspricht es, dass die Gegenpartei des Hauptverfahrens keiner Rechte verlustig geht, wenn sie sich zum Gesuch nicht äussert. Aus dem Verzicht auf eine Stellungnahme zum Gesuch um unentgeltliche Rechtspflege kann für den Hauptprozess nichts abgeleitet werden. Namentlich darf der Gegenpartei im Hauptprozess nicht etwa entgegengehalten werden, sie hätte mangels Bestreitung der Ausführungen des Gesuchstellers zu den Erfolgsaussichten dessen Behauptungen anerkannt. Die Gegenpartei des Hauptverfahrens würde ferner im umgekehrten Fall einer Gutheissung des Gesuchs um unentgeltliche Rechtspflege, nachdem sie sich zum Gesuch (ohne Bös- oder Mutwilligkeit) geäussert und einen Antrag gestellt hat, auch nicht mit einer Parteientschädigung an den Gesuchsteller belastet. Der durch das Gesuch verursachte anwaltliche Aufwand des Gesuchstellers ist vom Entschädigungsanspruch des unentgeltlichen Rechtsbeistandes umfasst (vgl. Bühler, a.a.O., N. 151 zu <ref-law>).
Da die Beschwerdegegnerin vorliegend nicht Partei des Gesuchsverfahrens um unentgeltliche Rechtspflege war, steht ihr für dieses Verfahren keine Parteientschädigung zu, obwohl sie zur Stellungnahme eingeladen wurde und von der Äusserungsmöglichkeit Gebrauch gemacht hat. Dies hat die Vorinstanz verkannt, indem sie im Rahmen des Nichteintretensbeschlusses der Beschwerdegegnerin eine Parteientschädigung zusprach, mit der die fakultative Stellungnahme zum Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege abgegolten werden sollte.
4.3. Sodann rügt der Beschwerdeführer zu Recht, dass die Vorinstanz mit der Zusprechung einer Parteientschädigung auch die Dispositionsmaxime verletzt hat. Im Geltungsbereich der ZPO wird - anders als im Beschwerdeverfahren vor Bundesgericht (<ref-ruling> E. 4 und 5; Bernard Corboz, Commentaire de la LTF, 2009, N. 53 zu <ref-law>; Geiser, a.a.O., N. 3 zu <ref-law>) - eine Parteientschädigung nicht von Amtes wegen, sondern nur auf Antrag festgesetzt. Die entsprechende Absicht des Gesetzgebers geht aus den Materialien hervor (Botschaft, a.a.O., 7296 zu Art. 102 und 103 ZPO) und wird durch den Wortlaut von <ref-law> zum Ausdruck gebracht, indem Absatz 2 im Gegensatz zu Absatz 1 über die Gerichtskosten gerade nicht vorschreibt, dass die Parteientschädigung von Amtes wegen zugesprochen wird. Die Doktrin ist sich denn auch einig in dieser Frage (Alexander Fischer, in: Baker & McKenzie [Hrsg.], Schweizerische Zivilprozessordnung, Bern 2010, N. 4 zu <ref-law>; Gasser/Rickli, Schweizerische Zivilprozessordnung, Kurzkommentar, 2010, N. 2 zu <ref-law>; David Jenny, in: Sutter-Somm/Hasenböhler/Leuenberger [Hrsg.], Kommentar zur Schweizerischen Zivilprozessordnung, 2. Aufl. 2013, N. 6 zu <ref-law>; Rüegg, a.a.O., N. 2 zu <ref-law>; Martin H. Sterchi, in: Berner Kommentar, Schweizerische Zivilprozessordnung, 2012, N. 6 zu <ref-law>; Tappy, a.a.O., N. 7 zu <ref-law>; Adrian Urwyler, in: Brunner/Gasser/Schwander [Hrsg.], Schweizerische Zivilprozessordnung, Kommentar, 2011, N. 4 zu <ref-law>).
Die Beschwerdegegnerin hat indessen keinen entsprechenden Antrag gestellt, wie der Beschwerdeführer geltend macht und von der Beschwerdegegnerin nicht bestritten wird. Die Dispositiv-Ziffer 4 des angefochtenen Beschlusses ist demnach auch aus diesem Grund aufzuheben, und der angefochtene Entscheid ist dahingehend neu zu fassen, dass keine Parteientschädigung zugesprochen wird.
5.
Aus dem Vorstehenden ergibt sich, dass die Beschwerde teilweise gutzuheissen ist. Da die Beschwerdegegnerin der Vorinstanz keinen Antrag auf Auferlegung der Kosten an den Beschwerdeführer oder Zusprechung einer Parteientschädigung stellte und sich nicht mit dem angefochtenen Beschluss identifizierte sowie im bundesgerichtlichen Verfahren auf eine Vernehmlassung und einen Antrag verzichtete, ist es nicht angebracht, ihr die Kosten und die Entschädigung zu auferlegen. Der Kanton Zürich darf nicht mit Gerichtskosten belastet werden (<ref-law>). Mithin erscheint es gerechtfertigt, auf die Erhebung von Kosten zu verzichten (<ref-law>) und den Kanton Zürich zu verpflichten, dem teilweise obsiegenden Beschwerdeführer eine reduzierte Parteientschädigung zu bezahlen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen.
Die Dispositiv-Ziffern 2 und 4 des Beschlusses des Handelsgerichts des Kantons Zürich vom 18. März 2013 werden aufgehoben und wie folgt neu gefasst:
"2. Die Gerichtsgebühr wird auf Fr. 2'000.-- festgesetzt."
"4. Es wird keine Parteientschädigung zugesprochen."
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 8. Juli 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Kölz