Sachverhalt:
A.
A.a. Am 13. August 2018 bewilligte das Bezirksgericht Meilen drei gegen A._ gerichtete Arrestbegehren der B._ AG für zwei Forderungen von je Fr. 994'500.-- plus Zinsen. Es erliess je einen Arrestbefehl an die Betreibungsämter Zürich 11 in Zürich, Pfannenstiel in Männedorf und Oberland in Interlaken. Befohlen wurde die Verarrestierung sämtlicher Guthaben und Vermögenswerte von A._ bei der Stiftung C._ (Betreibungsamt Zürich 11) und bei der Bank D._ (Betreibungsamt Oberland) sowie das bei Rechtsanwalt E._ hinterlegte Aktienzertifikat Nr. 1 der B._ AG über 25'000 Namenaktien (Betreibungsamt Pfannenstiel).
A.b. A._ erhob am 8. Oktober 2018 beim Bezirksgericht fristgerecht Einsprache gegen die drei Arrestbefehle. Die B._ AG erstattete am 28. November 2018 ihre Stellungnahme. Am 11. Januar 2019 zog A._ seine Einsprachen zurück.
A.c. Mit Verfügung vom 15. Januar 2019 schrieb das Bezirksgericht das Einspracheverfahren ab (Ziff. 1). Es auferlegte die Spruchgebühr von Fr. 1'000.-- A._ (Ziff. 2 und 3) und verpflichtete ihn zu einer Parteientschädigung an die B._ AG von Fr. 19'300.-- (Ziff. 4).
B.
Mit Beschwerde vom 28. Januar 2019 wandte sich A._ an das Obergericht des Kantons Zürich. Er beantragte die Aufhebung von Ziff. 4 der erstinstanzlichen Verfügung und die Festsetzung der Parteientschädigung gestützt auf den korrekten Streitwert auf maximal Fr. 8'183.15. Eventualiter sei die Sache zur Neufestsetzung der Parteientschädigung anhand des korrekten Streitwertes an das Bezirksgericht zurückzuweisen. Das Obergericht wies die Beschwerde mit Urteil vom 8. März 2019 ab.
C.
A._ ist mit Beschwerde in Zivilsachen evtl. subsidiärer Verfassungsbeschwerde vom 12. April 2019 an das Bundesgericht gelangt. Der Beschwerdeführer beantragt die Aufhebung des obergerichtlichen Urteils und die Festsetzung der Parteientschädigung an die B._ AG (Beschwerdegegnerin) gestützt auf den Schätzwert der verarrestierten Gegenstände auf Fr. 8'183.15.
Das Obergericht und die Beschwerdegegnerin haben auf eine Vernehmlassung verzichtet.

Erwägungen:
1.
1.1. Angefochten ist der Entscheid eines oberen kantonalen Gerichts, das als Rechtsmittelinstanz über die Parteientschädigung in einer Arrestsache entschieden hat (Art. 75 Abs. 1 und Art. 72 Abs. 2 lit. a BGG). Die gesetzlich erforderliche Streitwerthöhe (Fr. 30'000.--) wird nicht erreicht (<ref-law>). Damit ist die Beschwerde in Zivilsachen nur gegeben, sofern sich eine Rechtsfrage von grundsätzlicher Bedeutung stellt, was der Beschwerdeführer denn auch geltend macht (<ref-law>).
1.2. Der Beschwerdeführer hält selber zutreffend fest, dass der Entscheid über die Einsprache gegen einen Arrestbefehl wie der Arrestentscheid als vorsorgliche Massnahme im Sinne von <ref-law> gilt. Der Rechtsweg bezüglich der hier allein angefochtenen Entschädigungsregelung folgt jenem der Hauptsache. Damit kann der Beschwerdeführer einzig die Verletzung verfassungsmässiger Rechte geltend machen, wobei hier das Rügeprinzip gilt (<ref-law>; <ref-ruling> E. 1.2). Wie die Anwendung kantonaler Gesetze, welche ohnehin nicht frei überprüfbar sind (vgl. <ref-law>), wird die Anwendung von Bundesgesetzen im Rahmen von <ref-law> nur auf Willkür (<ref-law>) hin überprüft (Urteil 5A_492/2012 vom 13. März 2013 E. 2.3, nicht publ. in <ref-ruling>).
1.3. Die gleiche Rügenbeschränkung (Verletzung verfassungsmässiger Rechte) gilt für die subsidiäre Verfassungsbeschwerde (<ref-law>). Damit erübrigt sich die Prüfung, ob ein Anwendungsfall von <ref-law> vorliegt, denn der damit angestrebte Zweck, eine Rechtsfrage (von grundsätzlicher Bedeutung) mit uneingeschränkter Kognition beurteilen zu können, kann nicht erreicht werden (vgl. <ref-ruling> E. 1.3.3; Urteil 5D_46/2019 vom 18. Dezember 2019 E. 1.2). Die Eingabe ist folglich als subsidiäre Verfassungsbeschwerde entgegenzunehmen (<ref-law>).
1.4. Die Rüge der Verletzung verfassungsmässiger Rechte überprüft das Bundesgericht nur insofern, als die rechtsuchende Partei sie in der Beschwerde vorbringt und begründet (Art. 117 i.V.m. <ref-law>; vgl. zum Rügeprinzip <ref-ruling> E. 2.4; <ref-ruling> E. 1.4.2). Es legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Neue Tatsachen und Beweismittel sind nur zulässig, soweit der vorinstanzliche Entscheid dazu Anlass gibt (Art. 99 Abs. 1 i.V.m. <ref-law>).
2.
2.1. Die Vorinstanz verpflichtete den Beschwerdeführer zu einer Parteientschädigung an die Beschwerdegegnerin von Fr. 19'300.--. Sie ging für die Festlegung des Streitwertes von den Arrestforderungen und nicht vom Wert der Arrestgegenstände aus.
2.2. Nach Ansicht des Beschwerdeführers hätte der Arrestrichter den Streitwert von Amtes wegen anhand der betreibungsamtlichen Schätzung der Arrestgegenstände berechnen und die Parteientschädigung auf maximal Fr. 8'183.15 festsetzen sollen.
3.
Anlass zur vorliegenden Beschwerde gibt einzig die Festsetzung der Parteientschädigung im Arrest (einsprache) verfahren. Im Zentrum der Kritik steht dabei die Festlegung des massgeblichen Streitwertes. Nicht strittig ist hingegen die Auferlegung der Parteientschädigung zu Lasten des Beschwerdeführers.
3.1. Entscheide, die vom Arrestgericht getroffen werden, gehören zu den Angelegenheiten des SchKG, für welche das summarische Verfahren der ZPO zur Anwendung kommt (<ref-law>). Die Tarifhoheit für die Prozesskosten verbleibt bei den Kantonen (<ref-law>), soweit nicht eine Spezialregelung des Bundesrechts vorgeht. Dies ist hinsichtlich der Spruchgebühren in den Summarsachen des SchKG der Fall (<ref-law> i.V.m. <ref-law>; <ref-ruling> E. 4.2.2). Die Parteientschädigung an die obsiegende Partei (<ref-law>) richtet sich hingegen ausschliesslich nach dem kantonalen Tarif (<ref-ruling> E. 4.3).
3.2. Gemäss der im Kanton Zürich massgebenden Verordnung des Obergerichts über die Anwaltsgebühren vom 8. September 2010 (AnwGebV/ZH) setzt sich die Vergütung für die Parteivertretung durch Anwälte aus der Gebühr und den notwendigen Auslagen zusammen. Die Festsetzung der Gebühr richtet sich im Zivilprozess nach dem Streitwert bzw. dem Interessenwert (§ 2 Abs. 1 lit. a AnwGebV/ZH). Die entsprechende Grundgebühr kann je nach Verantwortung, Zeitaufwand oder Schwierigkeit des Falles um bis zu einem Drittel erhöht oder ermässigt werden (§ 4 Abs. 1 und 2 AnwGebV/ZH). Im summarischen Verfahren wird die Gebühr in der Regel auf zwei Drittel bis einem Fünftel ermässigt (§ 9 AnwGebV).
3.3. Zwar wird die Parteientschädigung nach dem kantonalem Tarif zugesprochen (Art. 105 Abs. 2 i.V.m. <ref-law>), indes erfolgt die Festlegung des hierfür massgeblichen Streitwertes - nach überwiegender Auffassung - nach Bundesrecht (<ref-law>; vgl. <ref-ruling> E. 4.3 a.E.), wonach ein kantonaler Vorbehalt für den sog. Kostenstreitwert nicht besteht (u.a. HALDY, La nouvelle procédure civile suisse, 2009, S. 9 f.; SUTTER-SOMM, Schweizerisches Zivilprozessrecht, 3. Aufl. 2017, Rz. 629; zuletzt BRIDEL, Les effets et la détermination de valeur litigieuse en procédure civile suisse, 2019, Rz. 118 ff., mit weiteren Hinweisen; vgl. Urteil 4A_289/2017 vom 21. Februar 2018 E. 3.3; Urteil 4A_45/2013 vom 6. Juni 2013 E. 3; Urteil 5A_261/2013 vom 19. September 2013 E. 3.3, 3.5). Zum Teil wurde entschieden, dass den Kantonen nicht verwehrt sei, den Kostenstreitwert auf andere Weise zu berechnen, als es die ZPO in Art. 91 ff. vorsieht (Urteil 5A_945/2017 vom 20. April 2018 E. 4.2; Urteil 5A_398/2018 vom 11. Dezember 2018 E. 4.2). Darauf ist nicht weiter einzugehen, da - zum einen - der Beschwerdeführer nicht geltend macht, die kantonale Instanz habe den Streitwert anders als nach den gemäss ZPO geltenden Kriterien festgesetzt, und - zum anderen - der Kostenstreitwert vorliegend ohnehin einzig unter dem Blickwinkel der Willkür geprüft werden kann (E. 1.2, 1.3).
3.4. Ob beim Streitwert auf die Arrestforderung oder auf den Schätzwert des Arrestobjektes abzustellen ist, wird in der Lehre kontrovers diskutiert und musste vom Bundesgericht bisher nicht abschliessend geklärt werden (<ref-ruling> E. 4.3.2 mit Hinweisen). Gemäss der bundesgerichtlichen Praxis ist die Bemessung des Streitwertes anhand des Wertes der Arrestgegenstände und, falls dieser nicht bekannt ist, nach der Arrestforderung nicht willkürlich (<ref-ruling> E. 4.3.3; Urteil 5A_849/2019 vom 16. Dezember 2019 E. 6.3). Dies ist beispielsweise bei der Verarrestierung von Bankguthaben der Fall, da die Bank erst nach rechtskräftiger Erledigung der Arresteinsprache über deren Höhe Auskunft geben muss (<ref-ruling> E. 2). Damit ist es auch nicht sachgerecht, auf die Arrestforderung abzustellen, sofern der Wert der Arrestgegenstände (beispielsweise aufgrund einer Schätzung im Rahmen einer vorangegangenen Pfändung) bekannt ist (vgl. Urteil 5A_28/2013 vom 15. April 2013 E. 2.4.2; vgl. auch <ref-ruling> E. 4.3.3).
3.5. Im vorliegenden Fall wurden von drei verschiedenen Betreibungsämtern Vermögenswerte des Beschwerdeführers verarrestiert. Das Betreibungsamt Oberland schätzte dessen Guthaben bei der Bank D._ auf insgesamt Fr. 3'984.75. Das Betreibungsamt Pfannenstiel bestätigte den Erhalt des Zertifikates Nr. 1 der B._ AG über 25'000 Namenaktien im Nennwert von je Fr. 10.--. Vom Betreibungsamt Zürich 11, welches die Guthaben des Beschwerdeführers bei der Stiftung C._ verarrestiert hatte, liegen eine Arresturkunde, die eine Schätzung oder anderweitige Angaben enthält, nicht vor. Der Beschwerdeführer, dem sein Guthaben wohl bekannt war, äusserte sich nicht zu dessen Höhe, wie die Vorinstanz zu Recht bemerkte.
3.6. Dem Beschwerdeführer kann daher nicht gefolgt werden, soweit er der Vorinstanz in allgemeiner Weise vorwirft, trotz Kenntnis des Wertes der Arrestgegenstände für die Bemessung des Streitwertes auf die Höhe der Arrestforderungen abgestellt zu haben. Bekannt waren einzig die (bei der Bank D._) verarrestierten Vermögensgegenstände, nicht aber die anderen Werte (Namenaktien und bei der Stiftung C._), wie im angefochtenen Urteil festgehalten wird. Vor diesem Hintergrund ist nicht nachvollziehbar, inwieweit die Vorinstanz in diesem Zusammenhang das rechtliche Gehör des Beschwerdeführers verletzt haben sollte, indem sie nicht weiter begründete, weshalb sie bei der Bemessung des Streitwertes die Arrestforderungen und den Wert der Arrestgegenstände als massgebend erachtete. Die Vorinstanz hatte aufgrund der tatsächlichen Umstände keinen Anlass weiter darzulegen, weshalb nicht vom zuvor (nur teilweise) festgestellten Schätzwert der Arrestgegenstände auszugehen sei. Eine Verletzung der Begründungspflicht liegt nicht vor (vgl. dazu <ref-ruling> E. 6.1). Soweit der Beschwerdeführer der Vorinstanz schliesslich vorwirft, ihm das Novenverbot entgegengehalten und damit sein rechtliches Gehör verletzt zu haben, kann ihm ebenso wenig gefolgt werden. Der Hinweis auf das Novenverbot gemäss <ref-law> (im Kostenbeschwerdeverfahren) erfolgte seitens der Vorinstanz einzig im Hinblick auf eine allfällige Stellungnahme des Beschwerdeführers und war daher nicht massgeblich für den Ausgang des Verfahrens, für welches die Vorinstanz fristgerechte Vorbringen vorausgesetzt hat.
3.7. In der Sache bringt der Beschwerdeführer vor, die Vorinstanz sei zur Festsetzung des Streitwertes nach pflichtgemässem Ermessen verpflichtet gewesen. Sie hätte für die Bemessung des Streitwertes auf die betreibungsamtliche Schätzung der verarrestierten Gegenstände abstellen müssen, die sich aus der Arresturkunde des Betreibungsamtes Oberland ergebe. Dabei handle es sich um einen gesetzlich vorgesehenen amtlichen Vorgang, der einen objektiven und verbindlichen Massstab verschaffe. Die Vorinstanz sei von der bundesgerichtlichen Rechtsprechung zur Bemessung des Streitwertes abgewichen und habe statt auf den (bekannten) Wert der Arrestgegenstände auf die Arrestforderungen abgestellt. Mit dieser Sichtweise übergeht der Beschwerdeführer, dass die bundesgerichtliche Praxis zur Festlegung des Streitwertes nur dann vom Wert der Arrestgegenstände ausgeht, soweit ein solcher (insgesamt) bekannt ist, was beispielsweise aufgrund der betreibungsamtlichen Schätzung angenommen werden kann. Fehlt es - wie vorliegend - teilweise an den erforderlichen Angaben, erweist sich die vorinstanzliche Festlegung des Streitwertes anhand der Arrestforderungen nicht als unhaltbar bzw. Verstoss gegen das Willkürverbot.
3.8. Soweit der Beschwerdeführer betreffend Streitwert zudem betont, der Streitgegenstand der Einsprache sei in jedem Fall nur der Arrestbeschlag, wie die Lehre überzeugend darlege, erweist sich sein Vorbringen im vorliegenden Fall nicht als zielführend. Das Bundesgericht hat zur Kontroverse bezüglich Streitwert bisher nicht abschliessend Stellung genommen (E. 3.4). Hingegen verpflichtet es den Dritten, in dessen Gewahrsam sich verarrestierte Gegenstände befinden, erst nach Ablauf der Einsprachefrist bzw. sobald ein rechtskräftiger Entscheid über die Arresteinsprache vorliegt, Auskunft zu erteilen (<ref-ruling> E. 2). Diese Rechtsprechung wird in der Lehre zwar teils kritisiert (u.a. REISER, in: Basler Kommentar, Bundesgesetz über Schuldbetreibung und Konkurs, 2. Aufl. 2010, N. 76 zu Art. 275), teils mit dem notwendigen Ausgleich verschiedener Interessen der Beteiligten gerechtfertigt (BOVEY, L'obligation des tiers de renseigner [...], JdT 2009 II S. 77). Im Hinblick auf die Festlegung des im konkreten Fall interessierenden Streitwertes würde eine Auseinandersetzung mit der damit verbundenen Problematik nichts bringen, da es an den notwendigen Angaben zum Wert der verarrestierten Gegenstände teilweise fehlt. Es bleibt daher dabei, dass in gewissen Fällen der Wert des Arrestgegenstandes nicht bereits mit dem Vollzug des Arrestes festgehalten werden kann und daher der Streitwert anhand der Arrestforderungen bestimmt werden muss. Daran ändert auch die Pflicht des Arrestrichters nichts, den Streitwert von Amtes wegen festzusetzen, da er auf die Angaben der Parteien und des Betreibungsamtes angewiesen ist. Keinesfalls kann ihm die die Pflicht zur Schätzung der Arrestgegenstände auferlegt werden, da diese vom Betreibungsamt vorzunehmen ist (<ref-law>). Nach dem Gesagten kann der Vorinstanz bei der Festsetzung der Parteientschädigung an die Beschwerdegegnerin im Ergebnis keine Willkür (<ref-law>) bzw. Verletzung verfassungsmässiger Rechte vorgeworfen werden.
4.
Der Beschwerde ist kein Erfolg beschieden. Ausgangsgemäss trägt der Beschwerdeführer die Gerichtskosten (<ref-law>). Die Beschwerdegegnerin hat sich nicht vernehmen lassen, womit ihr kein entschädigungspflichtiger Aufwand entstanden ist.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'500.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 20. Januar 2020
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Levante