Aus den Erwägungen:
4.2 Die Vorinstanz stellt sich auf den Standpunkt, den Beschwerdeführer gestützt auf Artikel 64 Absatz 1b in Verbindung mit Artikel 5 Absatz 1a des Bundesgesetzes über die Ausländerinnen und Ausländer (Ausländergesetz, AuG) vom 16. Dezember 2005 (fehlende Einreisebewilligung für die Einreise und den Verbleib mit Stellenantritt) rechtmässig aus der Schweiz wegzuweisen. Dabei übersieht sie, dass der Beschwerdeführer — wie dieser zu Recht vorbringt — unter Vorweisung seines biometrischen Passes berechtigt ist, visumsfrei in die Schweiz einzureisen und sich hier maximal 90 Tage aufzuhalten. Von dieser Möglichkeit hat er denn auch Gebrauch gemacht und ist am 2. November 2012 legal in die Schweiz eingereist (vgl. Einreisestempel des Flughafens Zürich). Der ihm hierfür zustehende 90-tägige Aufenthalt ist noch nicht abgelaufen. Von einer illegalen Einreise bzw. einem illegalen Aufenthalt in der Schweiz kann daher keine Rede sein.
4.3 Daran ändert auch das am 6. November 2012 gestellte Gesuch um Erteilung einer Aufenthaltsbewilligung zur Ausübung einer Erwerbstätigkeit nichts. Zwar trifft es zu, dass Ausländerinnen und Ausländer, welche für einen längeren Aufenthalt (über 90 Tage) und/oder mit der Absicht, eine Erwerbstätigkeit in der Schweiz aufzunehmen, einreisen wollen, hierzu ein Visum benötigen und dieses somit vorab bei der schweizerischen Vertretung im Heimatland beantragen müssen. Staatsangehörige von Albanien sind daher nur insoweit von der Visumspflicht befreit, als sie im Besitz eines biometrischen Reisepasses sind, es sich um einen kurzfristigen Aufenthalt im Schengenraum (max. 90 Tage) innerhalb einer Halbjahresperiode handelt und keine Erwerbstätigkeit ausgeübt wird (vgl. <http: www.bfm.admin.ch="" content="" bfm="" de="" home="" themen="" einreise="" faq.faq.html="">). Von der Vorinstanz wird jedoch nicht geltend gemacht, dass der Beschwerdeführer während seines visumsbefreiten Aufenthaltes in der Schweiz gearbeitet habe. Entsprechende Beweise liegen auch nicht vor. Die X-AG hat mit Schreiben und Formular zum Stellenantritt vom 6. November 2012 bei der Vorinstanz zwar für den Beschwerdeführer um Erteilung einer Aufenthaltsbewilligung zur Ausübung einer Erwerbstätigkeit ersucht. Dieses Gesuch darf aber nicht zum Schluss führen, dass der Beschwerdeführer bereits bei der Einreise eines Visums bedurft hätte, da er mit Erwerbsabsichten in die Schweiz gekommen sei. Auch wenn angesichts des Sachverhalts (erfolgloses Asylverfahren, Lebenspartnerin in der Schweiz, Einreise am 2. November 2012 und Einreichung eines Gesuchs um Stellenantritt am 6. November 2012) einiges dafür spricht, dass der Beschwerdeführer bereits vor der Einreise am 2. November 2012 die Absicht hatte, für längere Zeit oder gar dauerhaft in die Schweiz zurückzukehren und hier zu arbeiten, steht es ihm nach wie vor zu, sich bis zum Ablauf des 90-tägigen visumsbefreiten Aufenthaltes in der Schweiz aufzuhalten, zumindest solange er nicht (illegal) erwerbstätig ist oder andere Gründe seine Wegweisung erforderlich machen.
4.4 Um Situationen wie der vorliegenden angemessen entgegenzuwirken, ist es den Ausländerbehörden gemäss Artikel 17 Absatz 1 AuG jedoch erlaubt, mit der materiellen Prüfung eines Gesuchs um dauerhaften Aufenthalt, das von einem für einen vorübergehenden Aufenthalt rechtmässig eingereisten Ausländer gestellt wird, zuzuwarten, bis dieser — spätestens nach Ablauf dieses vorübergehenden Aufenthaltes — die Schweiz wieder verlassen hat. Somit wird sichergestellt, dass Ausländerinnen und Ausländer die allgemeinen Vorschriften für einen dauerhaften Aufenthalt nicht mittels des 90-tägigen visumsbefreiten Aufenthaltes umgehen. Beantragt der Beschwerdeführer also, nachdem er visumsbefreit in die Schweiz eingereist ist, eine Aufenthaltsbewilligung zur Ausübung einer Erwerbstätigkeit, ist auf sein Gesuch zwar einzutreten, das Verfahren aber bis zu seiner Wiederausreise zu sistieren. Erst wenn vom Ausland her alle Bedingungen für den Aufenthalt zur Ausübung einer Erwerbstätigkeit erfüllt sind und ein entsprechendes Visum erteilt wurde, ist der Beschwerdeführer befugt, in die Schweiz einzureisen, um eine Erwerbstätigkeit aufzunehmen. (Justiz- und Sicherheitsdepartement, 28. November 2012)
</http:>