Sachverhalt:
A.
A.a. A._ (Gesuchsteller, Beschwerdeführer) besitzt ein erhebliches Finanzvermögen, das ihm sein im Jahre 1975 verstorbener Vater hinterliess. Er finanziert sich seinen Lebensunterhalt aus dem Ertrag des ihm hinterlassenen Vermögens, das sich heute auf rund EUR 15 Mio. beläuft. Der Gesuchsteller besitzt keine Fachkenntnisse in der Vermögensanlage, weshalb er stets auf externe Berater angewiesen war. Das Vermögen wurde bis im Juni 2014 ununterbrochen zunächst bei der Bank C._ bzw. deren Rechtsnachfolgerin der Bank D._ und schliesslich, aufgrund einer Fusion der Bank D._ AG mit der Bank E._ AG im Jahre 2012, bei der Bank E._ verwahrt. Im Verlaufe der Finanzkrise im Jahre 2008 war der Gesuchsteller angesichts der Turbulenzen am Finanzmarkt höchst beunruhigt. Er zog im Herbst 2008 fast sein gesamtes Vermögen vom Markt ab und hinterlegte es in bar in einem Safe bei der Bank D._. Im Jahr 2010 zahlte er einen Teil wieder auf ein Konto bei der Bank D._ ein und investierte diesen.
F._ war bis 2012 Kundenberater bei der Bank D._ und seit 2004 für die Betreuung des Gesuchstellers zuständig. Als F._ zur B._ AG (damals G._ AG; Gesuchsgegnerin, Beschwerdegegnerin) wechselte, folgte ihm der Gesuchsteller und unterschrieb am 26. Juni 2013 einen Beratungsvertrag und eine von der Bank E._ vorbereitete Vermögensverwaltungsvollmacht zugunsten der Gesuchsgegnerin. Im Mai 2014 begab sich der Gesuchsteller zur Bank E._, entnahm dort dem Safe EUR 15'000.-- in bar und zahlte diesen Betrag auf sein Konto ein. Als sich die Turbulenzen auf den Anlagemärkten beruhigten, beschloss der Gesuchsteller seine sämtlichen Vermögenswerte aus dem Safe wieder bei der Bank E._ einzuzahlen, wobei er davon ausging, dass die Gesuchsgegnerin für ihn die Einzahlung der Vermögenswerte auf das bestehende Bankkonto bei der Bank E._ vornehmen könnte. Die Gesuchsgegnerin teilte ihm jedoch mit, dass es trotz "mehrmonatigen, intensiven Bemühungen" nicht möglich gewesen sei, die im Safe bei der Bank E._ liegenden Barbeträge auf die bestehenden Konten des Gesuchstellers bei der Bank E._ einzuzahlen.
A.b. Am 12. Mai 2014 eröffnete die Bank H._ SA, Zweigniederlassung U._, eine auf den Namen des Gesuchstellers lautende Kontobeziehung. Die Verwaltungsvollmacht des Gesuchstellers zugunsten der Gesuchsgegnerin für dieses Konto datiert vom gleichen Tag. Am 15. Mai 2014 unterzeichneten die Parteien einen Managementvertrag und der Gesuchsteller und seine Mutter unterschrieben eine Zahlungsinstruktion ("Instruction of Payment"). Letztere sah vor, dass 2 % der auf die Bank H._ SA übertragenen Vermögenswerte der neuseeländischen Offshore-Gesellschaft I._ Ltd. als Kommission überwiesen werden sollte. Wirtschaftlich Berechtigter dieser Offshore-Gesellschaft ist Rechtsanwalt J._. Rechtsanwalt J._, der den Gesuchsteller unter anderem in Steuerfragen bezüglich seiner Vermögenswerte beriet, wurde dem Gesuchsteller von F._ empfohlen.
A.c. Am 10. April 2015 machte der Gesuchsteller erstmals bei der Gesuchsgegnerin einen Rechenschafts- und Herausgabeanspruch geltend. Mit Antwortschreiben vom 24. April 2015 sandte die Gesuchsgegnerin dem Gesuchsteller eine Reihe von Unterlagen zu. Mit Schreiben vom 20. Mai 2015 hakte der Gesuchsteller nach und verwies ausdrücklich auf die durch F._ angeblich erfolgte Vermittlung der Depotbank. Die Gesuchsgegnerin bestritt in ihrer Antwort vom 11. Juni 2015, dass sie den Gesuchsteller beim Wechsel der Depotbank beraten habe. Mit Schreiben vom 7. August 2015 forderte der Gesuchsteller die Gesuchsgegnerin erneut auf, sämtliche Informationen im Zusammenhang mit ihrer Tätigkeit für den Gesuchsteller offenzulegen, insbesondere zu den dabei erfolgten Kommissionen. Mit Schreiben vom 19. August 2015 stellte sich die Gesuchsgegnerin auf den Standpunkt, keine weiteren Entschädigungen erhalten zu haben, da sie den Gesuchsteller nicht an die Bank H._ SA vermittelt habe. Am 8. Oktober 2015 forderte der Gesuchsteller erneute eine Rechenschaftsablegung und verwies wiederum auf die Tätigkeit der Gesuchsgegnerin im Rahmen der Vermittlung des Gesuchstellers an die Bank H._ SA. Mit Antwort vom 14. Oktober 2015 führte die Gesuchsgegnerin aus, dass es keine Unterlagen bezüglich einer Kommission gäbe.
B.
Der Gesuchsteller reichte am 29. Januar 2016 am Handelsgericht des Kantons Zürich das Gesuch um Rechtsschutz in klaren Fällen nach <ref-law> ein. Er beantragte zusammenfassend, die Gesuchsgegnerin sei unter Strafandrohung nach <ref-law> gegen ihre Organe im Unterlassungsfall zu verpflichten, Rechenschaft über ihre Tätigkeit im Zusammenhang mit der möglichen Einzahlung der bis im Mai 2013 in dem vom Gesuchsteller gemieteten Safe der Bank E._ gelegenen Bargelder auf die Konten des Gesuchstellers bei der Bank E._ abzulegen und ihm sämtliche Korrespondenz und Aufzeichnungen herauszugeben (Rechtsbegehren Ziff. 1 lit. a). Sodann sei die Beschwerdegegnerin zu verpflichten, Rechenschaft über ihre Tätigkeit im Zusammenhang mit der Vermittlung des Gesuchstellers an die Bank H._ SA abzulegen und Kopien sämtlicher diesbezüglicher Dokumente herauszugeben, sowie sämtliche Zahlungen oder sonstigen geldwerten Vorteile offenzulegen, die der Gesuchsgegnerin oder ihr nahestehenden Personen in diesem Zusammenhang zugekommen seien, und Kopien sämtlicher diesbezüglicher Dokumente oder Aufzeichnungen herauszugeben (Rechtsbegehren Ziff. 1 lit. b - i).
Mit Verfügung vom 10. Mai 2016 trat der Einzelrichter des Handelsgerichts auf das Begehren des Gesuchstellers nicht ein.
C.
Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, das Urteil des Einzelrichters am Handelsgericht des Kantons Zürich sei aufzuheben. Sodann beantragt er zusammenfassend, es sei die Beschwerdegegnerin unter Androhung der Bestrafung ihrer Organe nach <ref-law> im Unterlassungsfall zu verpflichten, Rechenschaft über ihre Tätigkeit im Zusammenhang mit der Vermittlung des Beschwerdeführers an die Bank H._ SA abzulegen und Kopien sämtlicher diesbezüglicher Dokumente herauszugeben, sowie sämtliche Zahlungen oder sonstigen geldwerten Vorteile offenzulegen, die der Gesuchsgegnerin oder ihr nahestehenden Personen in diesem Zusammenhang zugekommen seien, und Kopien sämtlicher diesbezüglicher Dokumente oder Aufzeichnungen herauszugeben.
Die Beschwerdegegnerin beantragt, die Beschwerde sei vollumfänglich abzuweisen, soweit darauf einzutreten sei. Die Vorinstanz verzichtete auf eine Vernehmlassung.
Die Parteien reichten Replik und Duplik ein.

Erwägungen:
1.
Die Sachurteilsvoraussetzungen der Beschwerde in Zivilsachen sind erfüllt und geben zu keinen Bemerkungen Anlass. Unter Vorbehalt einer rechtsgenüglichen Begründung (<ref-law>) ist daher auf die Beschwerde einzutreten.
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, andernfalls wird darauf nicht eingetreten (<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, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift 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. 89, 115 E. 2 S. 116).
2.2. Die Beschwerde ist innert der Beschwerdefrist vollständig begründet einzureichen (vgl. <ref-law>). Vor Bundesgericht findet in der Regel nur ein Schriftenwechsel statt (<ref-law>). Kommt es zu einem zweiten Schriftenwechsel, darf die beschwerdeführende Partei die Replik nicht dazu verwenden, ihre Beschwerde zu ergänzen oder zu verbessern (<ref-ruling> E. 1.7; <ref-ruling> E. 3.3.4). Mit Rügen, welche die beschwerdeführende Partei bereits in der Beschwerde hätte erheben können, ist sie nach Ablauf der Beschwerdefrist ausgeschlossen (<ref-ruling> E. 2.2; <ref-ruling> E. 1.7; <ref-ruling> E. 3.3.4 mit Hinweisen). Die Replik ist nur zu Darlegungen zu verwenden, zu denen die Ausführungen in der Vernehmlassung eines anderen Verfahrensbeteiligten Anlass geben (vgl. <ref-ruling> E. 2.2). Soweit der Beschwerdeführer in seiner Replik darüber hinausgeht, kann er nicht gehört werden.
2.3. 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>).
2.4. Gemäss <ref-law> dürfen neue Tatsachen und Beweismittel nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt, was in der Beschwerde näher darzulegen ist (<ref-ruling> E. 3 S. 395). Tatsachen oder Beweismittel, die sich auf das vorinstanzliche Prozessthema beziehen, jedoch erst nach dem angefochtenen Entscheid eingetreten oder entstanden sind (sog. echte Noven), sind vor Bundesgericht unbeachtlich (<ref-ruling> E. 2.1 S. 344; Urteil 4A_169/2016 vom 12. September 2016 E. 2.4).
Der Beschwerdeführer stützt sich in seiner Replik in mehrfacher Weise auf tatsächliche Elemente, die nach dem Tag der Fällung des angefochtenen Entscheids vom 10. Mai 2016 entstanden sind, namentlich die Schreiben vom 14. Juni 2016, 6. Juli 2016 und 18. August 2016. Diese echten Noven können nach dem Gesagten im bundesgerichtlichen Verfahren nicht berücksichtigt werden.
3.
Die Vorinstanz erwog, dass der Beschwerdeführer Rechenschafts- und Herausgabeansprüche nach <ref-law> geltend mache. Die Rechenschafts- und Auskunftspflicht des Beauftragten erstrecke sich auf das gesamte Auftragsverhältnis. Durch das Auftragsverhältnis werde die Pflicht des Beauftragten jedoch auch beschränkt: Die Rechenschafts- und Auskunftspflicht beziehe sich einzig auf die dem Beauftragten übertragenen Geschäfte und Dienste. Er müsse daher nur solche Auskünfte erteilen, die sich auf das konkrete Auftragsverhältnis beziehen würden.
Es sei vorliegend zwar unbestritten, so die Vorinstanz weiter, dass zwischen den Parteien eine auftragsrechtliche Beziehung nach Massgabe von <ref-law> bestanden habe. Umstritten sei jedoch der genaue Inhalt dieses Auftrags. Während der Beschwerdeführer vortragen lasse, dass das Auftragsverhältnis gerade darum geschlossen worden sei, um ihn dahingehend zu beraten, wann und wie sein Bargeld wieder auf ein Konto einbezahlt (und investiert) werden solle, bestreite die Beschwerdegegnerin jegliche vertragliche Verpflichtung eingegangen zu sein, dem Beschwerdeführer eine neue Depotbank zu suchen. Der Inhalt des Auftrags sei mithin nicht unbestritten. Sämtliche Rechtsbegehren des Beschwerdeführers würden jedoch eine Mandatsbeziehung zwischen den Parteien erfordern, die (zumindest auch) das Finden einer Depotbank für die entsprechenden Barmittel des Beschwerdeführers zum Inhalt habe. Es sei daher zu prüfen, ob anhand der eingereichten Unterlagen erstellt werden könne, dass ein dahingehendes Auftragsverhältnis, so wie es vom Beschwerdeführer vorgetragen werde, zwischen den Parteien erstellt werden könne.
Die Vorinstanz ging anschliessend ausführlich auf die vom Beschwerdeführer eingereichten Urkunden ein, so namentlich auf den Beratungsvertrag vom 26. Juni 2013, das Schreiben der Beschwerdegegnerin an die Rechtsvertreter des Beschwerdeführers [vom 19. August 2015], einen Auszug der Homepage der Beschwerdegegnerin, den "Kundenprüfungs-Report" der Bank H._ SA vom 12. Mai 2014, das Schreiben vom 11. Juni 2014 der Beschwerdegegnerin an die Bank H._ SA, die Zahlungsinstruktion vom 15. Mai 2015, den Managementvertrag vom 15. Mai 2014 und die weitere Korrespondenz der Parteien zwischen dem 10. April 2015 und dem 14. Oktober 2015 sowie diejenige zwischen dem Beschwerdeführer und der Anwaltskanzlei K._.
Die Vorinstanz kam dabei zusammenfassend zum Schluss, dass sich mit den Mitteln des summarischen Verfahrens weder abschliessend eruieren lasse, ob zwischen den Parteien ein entsprechendes Mandatsverhältnis bestanden habe, noch, ob aufgrund dieses Vertragsverhältnisses die Beschwerdegegnerin den Beschwerdeführer bei der Bank H._ SA tatsächlich eingeführt habe. Der hierfür notwendige Sachverhalt sei hinsichtlich beider Vorfragen unklar, weshalb kein Rechtsschutz in klaren Fällen gewährt werden könne.
4.
Der Beschwerdeführer machte seinen Rechenschafts- und Herausgabeanspruch nach <ref-law> gegenüber der Beschwerdegegnerin im Verfahren des Rechtsschutzes in klaren Fällen nach <ref-law> geltend. <ref-law> sieht vor, dass das Gericht Rechtsschutz im summarischen Verfahren gewährt, wenn zum einen der Sachverhalt unbestritten oder sofort beweisbar (lit. a) und zum anderen die Rechtslage klar ist (lit. b). Kann dieser Rechtsschutz nicht gewährt werden, so tritt das Gericht auf das Gesuch nicht ein (<ref-law>; <ref-ruling> E. 3.2 S. 264; <ref-ruling> E. 5).
Ein klarer Fall setzt demnach zum einen voraus, dass der Sachverhalt unbestritten oder sofort beweisbar ist (<ref-law>). Ein Sachverhalt ist dann sofort beweisbar, wenn er ohne zeitliche Verzögerung und ohne besonderen Aufwand nachgewiesen werden kann. Der Beweis ist - entsprechend <ref-law> - in der Regel durch Urkunden zu erbringen (<ref-ruling> E. 3.2 S. 26; <ref-ruling> E. 2.1.1 S. 125, 620 E. 5.1.1 S. 621).
Zum anderen setzt ein klarer Fall voraus, dass die Rechtslage klar ist (<ref-law>). Dies trifft zu, wenn sich die Rechtsfolge bei der Anwendung des Gesetzes unter Berücksichtigung der Lehre und Rechtsprechung ohne Weiteres ergibt und damit die Rechtsanwendung zu einem eindeutigen Ergebnis führt (<ref-ruling> E. 3.2 S. 26; <ref-ruling> E. 2.1.2; je mit Hinweisen).
5.
5.1. Der Beschwerdeführer rügt, die Vorinstanz habe <ref-law> falsch angewandt. Die Rechenschafts- und Informationspflicht gehe über den konkreten Umfang des zugrundliegenden Mandatsverhältnisses hinaus. Die ratio legis von <ref-law> verpflichte zur Information über alles im Zusammenhang mit dem Auftrag Erlangte. Die Rechenschafts- und Informationspflicht nach <ref-law> müsse sich als notwendige Grundlage der Herausgabepflicht grundsätzlich auf alle möglichen und allfälligen Vermögensvorteile beziehen, die im Zusammenhang mit dem Mandat erfolgt seien. Bestehe auch nur die Möglichkeit, dass ein Auftragnehmer im Zusammenhang mit dem zugrundeliegenden Auftragsverhältnis einen Vermögensvorteil erlangt habe, so müsse dem Beauftragten auch ein Anspruch auf Rechenschaftsablage und Information im entsprechenden, gleichen Umfang zugestanden werden. Eine derart enge Anwendung von <ref-law> wie sie die Vorinstanz verstehe, widerspreche nicht nur dem dem Auftragsrecht immanenten Grundprinzip, sondern auch der ratio legis der Bestimmung von <ref-law>, würde doch damit letztlich auch die Ablieferungs- bzw. Herausgabepflicht als essentiale des Auftragsrechts zu einer unechten Obligation werden. Denn nur wer Kenntnis habe über das "Wie und Was des Erlangten" könne überprüfen, ob die Ablieferungspflicht "richtig" erfüllt sei. Klares Recht sei daher, dass der Auskunftsanspruch auch dort bestehe, wo die Herausgabeansprüche nicht strikte auf dem Gegenstand des Mandats gründen würden, sondern damit in Zusammenhang stünden. Ein Zusammenhang bestehe bei einem "inneren Zusammenhang", unter anderem bei Gefahr eines Interessenkonflikts.
5.2. Wie der Beschwerdeführer richtig erkennt, hat der Beauftragte nach <ref-law> auf Verlangen jederzeit über seine Geschäftsführung Rechenschaft abzulegen und alles, was ihm infolge derselben aus irgendeinem Grunde zugekommen ist, zu erstatten (<ref-ruling> E. 4.1.2 mit Hinweisen). Das Bundesgericht hat dabei entschieden, dass der Umfang der Rechenschaftspflicht auf Belange des Auftragsverhältnisses beschränkt ist, wobei der Beauftragte den Auftraggeber vollständig und wahrheitsgetreu zu informieren und ihm alle Dokumente vorzulegen hat, die sich auf die im Interesse des Auftraggebers besorgten Geschäfte beziehen (<ref-ruling> E. 4.1.3 S. 54 mit Hinweis auf das Urteil C.59/1980 vom 17. Juni 1980 E. 2 [nach ZR: E. 1], in: ZR 80/1981 S. 73). In der Lehre wird davon ausgegangen, dass der Beauftragte nur solche Auskünfte erteilen muss, die sich auf das konkrete Auftragsverhältnis beziehen (vgl. Walter Fellmann, Berner Kommentar, 1992, N. 25 zu <ref-law>). Von diesem Rechtsverständnis ging auch die Vorinstanz aus.
Demgegenüber postuliert der Beschwerdeführer, der Umfang der Rechenschaftspflicht nach <ref-law> erstrecke sich über die Belange des konkreten Auftragsverhältnisses hinaus auch auf Gegenstände, die mit dem Auftragsverhältnis lediglich in Zusammenhang stünden. Er meint, unter Zugrundelegung dieses von ihm postulierten Rechtsverständnisses sei die Sachlage klar im Sinne von <ref-law>.
Dem kann nicht gefolgt werden. Das Verfahren des Rechtsschutzes in klaren Fällen setzt voraus, dass die Rechtslage klar ist. Der Beschwerdeführer zeigt aber nicht auf, dass die Vorinstanz die geltende Rechtslage verkannt hätte, und die Rechtslage im Sinne seines hier postulierten Verständnisses lauten würde, indem er sich bloss pauschal auf die "ratio legis" von <ref-law> und ein dem Auftragsrecht "immanentes Grundprinzip" beruft. Darauf kann daher nicht abgestellt werden. Dass der Sachverhalt unter Zugrundelegung des zutreffenden Rechtsverständnisses der Vorinstanz klar wäre, macht der Beschwerdeführer nicht geltend.
Demnach ist es nicht zu beanstanden, dass die Vorinstanz dem Beschwerdeführer mangels klarer Sachlage den Rechtsschutz in klaren Fällen nach <ref-law> verweigert hat und auf das entsprechende Gesuch des Beschwerdeführers nicht eingetreten ist.
6.
Die Beschwerde ist abzuweisen, soweit auf sie eingetreten werden kann. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 1 BGG).

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