Sachverhalt: A. Zwischen X._ (geb. 1960, britischer Staatsangehöriger) und dessen Ehefrau A._ (geb. 1967, brasilianische Staatsangehörige) ist seit 2008 ein Scheidungsverfahren vor dem Bezirksgericht Zürich hängig. Seit Juli 2009 ist Bezirksrichterin Y._ für den Fall zuständig. B. Am 17. Oktober 2012 verlangte X._, Y._ habe in den Ausstand zu treten. Diese überwies die Angelegenheit an die Verwaltungskommission des Obergerichts des Kantons Zürich, welches beide Seiten anhörte. Mit Entscheid vom 7. Februar 2013 trat die Verwaltungskommission auf das Ablehnungsbegehren nicht ein. C. Den Nichteintretensentscheid focht X._ am 22. Februar 2013 bei der Rekurskommission des Obergerichts an und beantragte, dieser sei aufzuheben. Es sei unter Kosten- und Entschädigungsfolgen festzustellen, dass Bezirksrichterin Y._ als befangen erscheine und in den Ausstand zu treten habe. Die Rekurskommission wies die Beschwerde gegen den Nichteintretensentscheid der Verwaltungskommission am 11. April 2013 ab, soweit sie darauf eintrat, und auferlegte die Kosten des Beschwerdeverfahrens X._. D. Gegen dieses Urteil gelangte X._ mit Beschwerde in Zivilsachen und subsidiärer Verfassungsbeschwerde (Postaufgabe am 15. Mai 2013) an das Bundesgericht. Er verlangt, der Entscheid vom 11. April 2013 sei aufzuheben und die Vorinstanz sei anzuweisen, Bezirksrichterin Y._ im Scheidungsprozess auszuschliessen. Sinngemäss verlangt er weiter, die Verfahrenskosten seien der Ehefrau aufzuerlegen und diese habe ihm eine Parteientschädigung zu bezahlen. Das Bundesgericht hat die Akten, in der Sache selbst aber keine Vernehmlassungen eingeholt. E. Im Zusammenhang mit dem Scheidungsverfahren ist der Beschwerdeführer bereits mehrmals an das Bundesgericht gelangt (vorsorgliche Massnahmen, Rechtsöffnungsverfahren betreffend Unterhalt), wobei auf seine Beschwerden jeweils nicht eingetreten wurde (vgl. Urteile 5A_103/2011 vom 23. Mai 2011, 5A_49/2012 vom 19. Januar 2012, 5A_786/2011 vom 26. Januar 2012 und 5A_433/2012 vom 21. August 2012).