Sachverhalt: A. Auf Ersuchen von Y._ bewilligte das Einzelgericht im summarischen Verfahren des Bezirks Meilen mit Befehlen vom 2., 6. und 8. September 2010 gestützt auf Art. 271 Abs. 1 Ziff. 4 SchKG für den Betrag von insgesamt Fr. 821'810.-- zuzüglich Zinsen den Arrest der bei X._ zuvor provisorisch gepfändeten Vermögenswerte. Als Forderungsurkunde wurde ein Urteil des Oberlandesgerichts Düsseldorf vom 13. September 2007 bezeichnet. Das Betreibungsamt Stäfa-Hombrechtikon vollzog den Arrest am 10. September 2010. Hinsichtlich der beschlagnahmten Gegenstände übernahm es den Schätzungswert der provisorischen Pfändung in der Höhe von Fr. 242'500.--. B. Dagegen wandte sich X._ an das Bezirksgericht Meilen, welches seine Arresteinsprache am 14. September 2012 abwies. Die Entscheidgebühr wurde auf Fr. 1'000.-- festgelegt. Das Obergericht des Kantons Zürich wies die Beschwerde von X._ gegen das bezirksgerichtliche Urteil am 3. Dezember 2012 ab. Es setzte die zweitinstanzliche Entscheidgebühr auf Fr. 6'700.-- fest (Dispositivziff. 2) und verrechnete sie mit dem geleisteten Vorschuss (Dispositivziff. 3). C. X._ ist mit Beschwerde in Zivilsachen vom 9. Januar 2013 an das Bundesgericht gelangt. Der Beschwerdeführer beantragt die Aufhebung des obergerichtlichen Urteils und die Festsetzung der zweitinstanzlichen Entscheidgebühr auf Fr. 3'612.--. Eventualiter sei die Sache an die Vorinstanz zur Neufestsetzung der zweitinstanzlichen Entscheidgebühr anhand des korrekten Streitwertes zurückzuweisen. Y._ hat am 8. März 2013 (Postaufgabe) eine Beschwerdeantwort eingereicht, ohne einen formellen Antrag zu stellen. Das Obergericht hat auf eine Vernehmlassung verzichtet.