Sachverhalt:
A.
Der aus Bangladesch stammende B.X._ (geb. 1970) reiste am 13. Oktober 2004 von Italien in die Schweiz ein und heiratete gleichentags die aus Thailand stammende Schweizer Bürgerin A.X._ (geb. 1955), die er am 4. März 2004 in Basel kennengelernt hatte. B.X._ nahm Wohnsitz im Kanton Zürich und erhielt die Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau, welche jedoch weiterhin in Basel lebte. Am 29. Juli 2009 wies das Migrationsamt des Kantons Zürich das Gesuch um Verlängerung der Aufenthaltsbewilligung ab, weil eine Scheinehe vorliege. Das Bundesgericht bestätigte diesen Entscheid letztinstanzlich mit Urteil 2C_707/2011 vom 3. Juni 2012, worauf das Migrationsamt des Kantons Zürich die Wegweisung verfügte.
Auf ein am 10. August 2012 gestelltes Gesuch um Bewilligung des Kantonswechsels, worin die Eheleute X._ geltend machten, sie wollten nun in Basel einen gemeinsamen ehelichen Wohnsitz begründen, trat das Migrationsamt des Kantons Basel-Stadt nicht ein; die dagegen erhobenen kantonalen Rechtsmittel blieben erfolglos.
B.
Am 13. September 2012 beantragten die Eheleute X._ die Erteilung einer Aufenthaltsbewilligung für B.X._ im Rahmen des Familiennachzugs. Das Migrationsamt des Kantons Basel-Stadt trat am 3. Oktober 2012 auf das Gesuch nicht ein. Die Eheleute X._ fochten den Nichteintretensentscheid beim Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt (nachfolgend: Justiz- und Sicherheitsdepartement) an und beantragten als vorsorgliche Massnahme, B.X._ sei der Aufenthalt im Kanton Basel-Stadt bis zum rechtskräftigen Entscheid zu gestatten. Das Justiz- und Sicherheitsdepartement wies das Gesuch am 19. Oktober 2012 ab. Das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht (nachfolgend: Appellationsgericht) bestätigte diesen Entscheid mit Urteil vom 23. Januar 2013.
C.
Mit Eingabe vom 2. Februar 2013 erheben A.X._ und B.X._ "Beschwerde und Verfassungsbeschwerde" beim Bundesgericht mit dem Rechtsbegehren, der angefochtene Entscheid sei aufzuheben und B.X._ sei im Sinn einer vorsorglichen Massnahme während des laufenden Verfahrens der Verbleib bei seiner Ehefrau bzw. der Aufenthalt im Kanton Basel-Stadt bis zum rechtskräftigen Entscheid zu gestatten.
Das Appellationsgericht, das Justiz- und Sicherheitsdepartement und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
Mit Präsidialverfügung vom 22. April 2013 ist der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt worden.

Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1 S. 475; <ref-ruling> E. 1).
1.1. Auf dem Gebiet des Ausländerrechts ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gemäss <ref-law> unzulässig gegen Entscheide betreffend die Erteilung oder Verweigerung von Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. An einem Rechtsanspruch fehlt es dann, wenn keine gesetzliche Norm die Voraussetzungen der Bewilligungserteilung näher regelt und diesbezügliche Kriterien aufstellt (<ref-ruling> E. 6.5 S. 198). Für das Eintreten genügt ein potenzieller Anspruch im Rahmen der gesetzlichen Bestimmungen (<ref-ruling> E. 2.5 S. 315; <ref-ruling> E. 1.1 S. 179); der Anspruch muss jedoch ernsthaft in Betracht kommen (Urteil 2C_769/2012 vom 22. Oktober 2012 E. 1.1 mit Hinweisen).
1.2. Die Beschwerdeführenden berufen sich auf Art. 42 Abs. 1 AuG (SR 142.20) und Art. 8 Ziff. 1 EMRK, indem sie auf ihre achtjährige Ehe verweisen.
Das Bundesgericht hat in seinem Urteil vom 3. Juni 2012 rechtskräftig entschieden, dass die Beschwerdeführenden eine Scheinehe eingegangen waren. Darauf ist nicht zurückzukommen. Die Beschwerdeführenden machen jedoch geltend, sie würden zusammenwohnen und die Beziehung werde aktenkundig gelebt, weshalb die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig sei.
1.3. Wird im Verfahren vor dem Bundesgericht ein Entscheid angefochten, der die Verweigerung oder den Entzug einer ausländerrechtlichen Bewilligung bestätigt, reicht es für die Berufung auf Art. 42 Abs. 1 AuG im Rahmen der Eintretensfrage aus, wenn formell eine Ehe besteht (vgl. <ref-ruling> E. 1.1.2 S. 148 [noch zu Art. 7 ANAG; BS 1 121]); bei der Anrufung von Art. 8 Ziff. 1 EMRK wird immerhin verlangt, dass die beschwerdeführende Partei als mögliche Trägerin des Rechts auf Achtung des Familienlebens berührt ist und eine Verletzung dieses (behaupteten) Rechts in vertretbarer Weise geltend macht (vgl. Urteil 2C_932/2011 vom 7. Juni 2012 E. 1.2.1). Es ist eine Frage der materiellen Beurteilung, ob die Ehe im massgeblichen Zeitpunkt tatsächlich gelebt wurde oder die Berufung darauf rechtsmissbräuchlich ist (BGE <ref-ruling> E. 1.1 S. 179; 126 II 265 E. 1b).
Im vorliegenden Fall ist rechtskräftig und höchstrichterlich entschieden worden, dass eine Umgehungsehe vorliegt. Die materielle Behandlung dieser Frage ist damit bereits erfolgt, weshalb ein Rechtsanspruch auf Familiennachzug ohne entgegenstehende Indizien fraglich erscheint. Die in <ref-law> statuierte Pflicht, die Beschwerde zu begründen, gilt auch in Bezug auf nicht evidente Eintretensvoraussetzungen (Urteil 2C_1020/2012 vom 15. Oktober 2012 E. 2.2 mit Hinweisen).
1.4. Im Rahmen eines erneut gestellten Familiennachzugsgesuchs können grundsätzlich neue Tatsachen geltend gemacht werden, welche ein Rückkommen auf die rechtskräftig gewordene Wegweisung rechtfertigen (vgl. Urteil 2C_683/2012 vom 19. März 2013 E. 3.1). Im Bereich der (rechtskräftig festgestellten) Umgehungsehe stellt der sogenannte amor superveniens, die nachträglich eingetretene echte Ehegemeinschaft, eine solche neue Tatsache dar (zum amor superveniens im Rahmen eines Wiedererwägungsgesuchs vgl. Urteil 2C_574/2012 vom 19. Februar 2013 E. 4).
Die Beschwerdeführenden machen als Indiz für das Vorliegen einer tatsächlichen Ehe den - erst nach der Wegweisung begründeten - gemeinsamen Wohnsitz in Basel geltend. Sie führen dazu aus, sie hätten sich der Ansicht des Bundesgerichts gebeugt und in der Folge einen neuen gemeinsamen Wohnsitz in Basel begründet.
Die Beschwerdeführenden weisen (zutreffend) darauf hin, eine rechtsmissbräuchlich geschlossene Ehe könne geheilt werden, wenn gegenseitige Zuneigung, der Wunsch nach Zusammenleben und eine tatsächlich gelebte Ehe vorliegen würden. Sie machen aber nicht geltend, dass in ihrem Fall ein sogenannter amor supervenienseingetreten wäre. Sie beteuern im Gegenteil, dass sie von Beginn an eine tatsächliche Ehegemeinschaft geführt hätten, und bestreiten die rechtskräftigen Feststellungen des Bundesgerichts hinsichtlich der Umgehungsehe. Die Beschwerdeführenden argumentieren sodann, wenn sogar eine rechtsmissbräuchliche Ehe geheilt werden könne, so müsse dies in ihrem Fall umso mehr gelten, da ihre Ehe über Jahre hinweg nur wegen der Arbeitsstellen zeitweise getrennt gelebt worden sei.
1.5. Mit diesen Ausführungen bestreiten die Beschwerdeführenden wiederum die rechtskräftigen Feststellungen des Bundesgerichts. Sie machen hingegen nicht geltend, die ehelichen Verhältnisse hätten sich seit dem 14. Juli 2011 (Datum des kantonalen Verwaltungsgerichtsurteils, welcher das Ende des vom Bundesgericht überprüften Zeitraums markiert) geändert. Vielmehr räumen sie selbst ein, sie hätten sich dem Urteil des Bundesgerichts "gebeugt" und deshalb eine gemeinsame Wohnung in Basel gemietet. Diese rein äusserliche Massnahme vermag jedoch aus der rechtskräftig festgestellten Scheinehe keine tatsächliche Ehegemeinschaft zu machen, wie auch die Vorinstanz zutreffend erwogen hat. Weil die Beschwerdeführenden dem Umstand des gemeinsamen (faktischen) Wohnsitzes keine Bedeutung zumessen, welche die Ehegemeinschaft als solche betrifft, kann darin keine rechtserhebliche neue Tatsache erblickt werden: Nicht die Wohnverhältnisse allein sind massgeblich, sondern die ehelichen Verhältnisse. Die Behauptungslast dafür, dass letztere sich in qualifizierter Weise geändert haben, liegt bei den Beschwerdeführenden (Urteil 2C_574/2012 vom 19. Februar 2013 E. 4.2). Diese aber legen keine Indizien vor, welche auf das Vorhandensein eines amor superveniens deuten würden; solche sind auch nicht ersichtlich. Es besteht somit kein Anlass zur Annahme, die rechtsmissbräuchlich geschlossene Ehe habe sich in eine tatsächlich gelebte Ehegemeinschaft gewandelt.
1.6. Die vorstehenden Erwägungen führen zum Schluss, dass das Erfordernis, wonach der potenzielle Rechtsanspruch ernsthaft in Betracht fallen muss (vgl. E. 1.1), hier nicht erfüllt ist. Nachdem das Bundesgericht rechtskräftig festgehalten hat, dass eine Scheinehe vorliegt, und die Beschwerdeführenden keine Tatsachen geltend machen, welche eine nunmehr echte Ehegemeinschaft möglich erscheinen lassen, sondern im Gegenteil einräumen, sie hätten sich mit der gemeinsamen Wohnsitznahme lediglich dem Urteil des Bundesgerichts "gebeugt", scheidet eine Berufung auf Art. 8 Ziff. 1 EMRK bzw. Art. 42 Abs. 1 AuG aus.
1.7. Nach dem Gesagten ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht zulässig.
2.
Zu prüfen bleibt in Anwendung von <ref-law> die Zulässigkeit der subsidiären Verfassungsbeschwerde.
2.1. Gemäss <ref-law> ist zur Verfassungsbeschwerde berechtigt, wer ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids hat. Nach der Lehre und Rechtsprechung ist in der Sache auch die subsidiäre Verfassungsbeschwerde ausgeschlossen, wenn kein Rechtsanspruch auf eine ausländerrechtliche Bewilligung besteht ( PETER UEBERSAX, Einreise und Anwesenheit, in: Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], Ausländerrecht, 2. Aufl. 2009, S. 305; <ref-ruling> E. 2 S. 308; <ref-ruling> E. 6.1 S. 197 f.).
2.2. Trotz fehlender Legitimation in der Sache kann die betroffene Person die Verletzung von Parteirechten rügen, deren Missachtung einer formellen Rechtsverweigerung gleichkommt (sog. "Star"-Praxis). Unzulässig sind Vorbringen, die im Ergebnis wiederum auf eine materielle Überprüfung des angefochtenen Entscheids abzielen, wie die Behauptung, die Begründung sei unvollständig oder zu wenig differenziert bzw. die Vorinstanz habe sich nicht oder in willkürlicher Weise mit den Argumenten der Partei auseinandergesetzt und Beweisanträge in offensichtlich unhaltbarer antizipierter Beweiswürdigung abgelehnt (<ref-ruling> E. 2 S. 308 mit weiteren Hinweisen).
2.3. Die Beschwerdeführenden machen geltend, angesichts der "offensichtlich vorliegenden neuen Indizien" liege eine Rechtsverweigerung vor; zudem habe die Vorinstanz den Untersuchungsgrundsatz und den Anspruch auf rechtliches Gehör verletzt, indem sie die neue Situation der Beschwerdeführenden nicht weiter beachtet bzw. sie dazu nicht näher gehört habe.
Diesen Ausführungen kann nicht beigepflichtet werden. Von einer Rechtsverweigerung kann angesichts des sorgfältig begründeten angefochtenen Urteils keine Rede sein. Die Vorinstanz hat weder den Untersuchungsgrundsatz noch das rechtliche Gehör verletzt, wenn sie dem nunmehr gemeinsamen Wohnsitz der Beschwerdeführenden unter Hinweis auf den Zeitpunkt (drei Monate nach der Wegweisung) nur untergeordnete Bedeutung beigemessen und darauf hingewiesen hat, die Verhältnisse hätten sich nicht in rechtserheblicher Weise geändert und weitere Hinweise auf eine "echte" Ehe würden nicht vorliegen. Bei dieser Ausgangslage und mit Blick auf die Tatsache, dass ein Entscheid betreffend vorsorgliche Massnahmen zu überprüfen war, durfte die Vorinstanz die Interessenabwägung ohne zusätzliche Beweismassnahmen und insbesondere ohne Anhörung vornehmen. Die formellen Rügen der Beschwerdeführenden sind unbegründet.
2.4. Die Verfassungsbeschwerde ist daher abzuweisen, soweit darauf einzutreten ist.
3.
Aus den vorstehenden Erwägungen ergibt sich, dass auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht einzutreten ist und die subsidiäre Verfassungsbeschwerde abzuweisen ist, soweit darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens tragen die unterliegenden Beschwerdeführenden die Gerichtskosten solidarisch (Art. 66 Abs. 1 und 5 BGG); eine Parteientschädigung ist nicht zuzusprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird nicht eingetreten.
2.
Die subsidiäre Verfassungsbeschwerde wird abgewiesen, soweit darauf eingetreten wird.
3.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 1. Juli 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Genner