Sachverhalt: A. A.a. X._, geb. 5. Juli 1974, Staatsangehöriger von Bangladesh, heiratete in seiner Heimat am 30. November 1999 die Schweizerin Z._, geboren 1970. Am 31. Mai 2000 reiste X._ in die Schweiz und erhielt in der Folge eine mehrfach verlängerte Aufenthaltsbewilligung und am 20. Juni 2005 die Niederlassungsbewilligung. Mit Urteil des Bezirksgerichts Zürich vom 14. Juli 2006 wurde die Ehe zwischen X._ und Z._ geschieden. A.b. Am 18. Juni 2008 ersuchte Y._, geboren 21. Februar 1976, die Schweizer Botschaft in Dhaka um Ausstellung eines Visums zur Einreise in die Schweiz. Dabei gab sie an, sie habe am 17. November 2006 in Bangladesh X._ geheiratet. A.c. Mit Verfügung vom 4. Dezember 2009 widerrief die Sicherheitsdirektion (Migrationsamt) des Kantons Zürich die Niederlassungsbewilligung X._s und setzte ihm eine Frist bis 31. März 2010, um die Schweiz zu verlassen; zugleich wies sie das Einreisegesuch Y._s ab. Zur Begründung führte sie aus, X._ sei die Ehe mit Z._ aus migrationsrechtlichen Motiven eingegangen. Nachdem der Regierungsrat des Kantons Zürich einen dagegen erhobenen Rekurs teilweise gutgeheissen und die Sache zu ergänzender Abklärung an das Migrationsamt zurückgewiesen hatte, widerrief dieses am 24. Januar 2012 erneut die Niederlassungsbewilligung X._s und wies es das Gesuch Y._s um Einreise ab. B. Die dagegen erhobenen kantonalen Rechtsmittel blieben erfolglos (Entscheid der Sicherheitsdirektion vom 6. August 2012, Urteil des Verwaltungsgerichts des Kantons Zürich vom 28. Januar 2013). C. X._ und Y._ erheben mit Eingabe vom 14. März 2013 beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten und Verfassungsbeschwerde mit dem Rechtsbegehren, in Aufhebung des angefochtenen Entscheids sei X._ die Niederlassungsbewilligung zu belassen und Y._ die Bewilligung zur Einreise in die Schweiz zu erteilen. Zudem beantragen sie Erteilung der unentgeltlichen Rechtspflege. D. Mit Verfügung vom 19. März 2013 wies das Bundesgericht das Gesuch um unentgeltliche Rechtspflege und Verbeiständung mangels nachgewiesener Bedürftigkeit ab, worauf X._ und Y._ den Kostenvorschuss einbezahlten. E. Mit Verfügung des Präsidenten der II. öffentlich-rechtlichen Abteilung des Bundesgerichts vom 25. März 2013 wurde der Beschwerde die aufschiebende Wirkung zuerkannt. Verwaltungsgericht und Sicherheitsdirektion des Kantons Zürich verzichten auf Vernehmlassung. Das Bundesamt für Justiz beantragt Abweisung der Beschwerde. 