Sachverhalt:
A.
A.a. Im August 2006 stellte A._ (Kläger, Beschwerdeführer), mazedonischer Staatsangehöriger, beim Amt für Migration des Kantons Luzern (nachfolgend AfM Luzern) ein Gesuch um Verlängerung seiner Aufenthaltsbewilligung, wobei er ab März 2007 Rechtsanwalt Dr. B._ (Beklagter, Beschwerdegegner) mit der Wahrung seiner Interessen beauftragte. Nach diversen Abklärungen sowie einem vorübergehenden interkantonalen Wohnortwechsel des Klägers lehnte das AfM Luzern im Dezember 2010 das Gesuch mit der Begründung ab, bei der im April 2003 zwischen dem Kläger und der schweizerischen Staatsangehörigen C._ geschlossenen Ehe handle es sich um eine Scheinehe; zumindest aber berufe sich der Kläger rechtsmissbräuchlich auf diese nur noch formell bestehende Ehe. Das vom Kläger mit Beschwerde angerufene Justiz- und Sicherheitsdepartement des Kantons Luzern bestätigte diese Verfügung am 16. Juni 2011.
A.b. Hiergegen erhob der Kläger, nach wie vor vertreten durch den Beklagten, Verwaltungsgerichtsbeschwerde beim Verwaltungsgericht des Kantons Luzern. Die Aufforderung zur Leistung des Gerichtskostenvorschusses bis am 5. August 2011 leitete der Beklagte am 22. Juli 2011 an den Kläger weiter, machte ihn zugleich auf die Säumnisfolgen aufmerksam und wies ihn an, ihm bis am 3. August 2011 eine Kopie der Einzahlungsquittung zukommen zu lassen. Da der Kläger zu dieser Zeit in Mazedonien war, nahm sein Bruder das Schreiben entgegen und setzte sich am 11. August 2011 mit dem Büro des Beklagten in Verbindung. Das gleichentags eingereichte Wiederherstellungsgesuch wies das Verwaltungsgericht am 17. August 2011 ab und trat zugleich nicht auf die Beschwerde ein, da der Kostenvorschuss nicht fristgerecht, sondern erst am 15. August 2011 bei ihm eingegangen war. Der Kläger, nunmehr vertreten durch seinen jetzigen Rechtsvertreter, führte dagegen erfolglos Beschwerde beim Bundesgericht. Seit dem 1. November 2011 lebt der Kläger wieder in Mazedonien.
B.
Nach fruchtlosem Schlichtungsverfahren reichte der Kläger am 21. Mai 2012 beim Bezirksgericht Plessur Klage ein, mit welcher er vom Beklagten die Zahlung von Fr. 593'471.85 nebst Zins verlangte. Das Bezirksgericht hiess die Klage im Umfang von Fr. 23'385.30 nebst Zins gut.
Der Beklagte erhob bezüglich der Verteilung der Prozesskosten Beschwerde beim Kantonsgericht von Graubünden, während der Kläger beim selben Gericht Berufung einreichte mit den Begehren, das Urteil des Bezirksgerichts sei aufzuheben und der Beklagte sei zur Zahlung von Fr. 593'414.-- nebst Zins zu verpflichten. Mit Urteil vom 14. Dezember 2015 hiess das Kantonsgericht die Beschwerde des Beklagten gut; die Berufung des Klägers wies es hingegen ab.
C.
Mit Beschwerde in Zivilsachen beantragte der Beschwerdeführer dem Bundesgericht, das Urteil des Kantonsgerichts sei kostenfällig aufzuheben und der Beschwerdegegner sei zur Zahlung von Fr. 593'414.-- nebst Zins zu verpflichten; weiter sei die Sache "zur masslichen Beurteilung" und zur Neufestsetzung der erst- und zweitinstanzlichen Kosten an das Bezirksgericht, eventuell an das Kantonsgericht zurückzuweisen. Gleichzeitig stellte er ein Gesuch um unentgeltliche Rechtspflege im bundesgerichtlichen Verfahren.
Nach Erhalt der Eingangsanzeige ersuchte der Beschwerdegegner um Sicherstellung der Parteikosten, sofern entweder der Beschwerdeführer kein Gesuch um unentgeltliche Rechtspflege eingereicht haben sollte oder aber ein solches infolge Aussichtslosigkeit abgewiesen würde.
Es wurden keine Vernehmlassungen eingeholt.

Erwägungen:
1.
Da die Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde in Zivilsachen unter Vorbehalt einer rechtsgenüglichen Begründung (<ref-law>) einzutreten.
2.
2.1. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Mit Blick auf die allgemeinen Begründungsanforderungen an eine Beschwerde (Art. 42 Abs. 1 und 2 BGG) behandelt es aber grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind; es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 2 S. 88 f. mit Hinweisen). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.1 S. 53 mit Hinweis).
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den streitgegenständlichen Lebenssachverhalt als auch jene über den Ablauf des vorinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (<ref-ruling> E. 1.3.1 S. 17 f. mit Hinweisen). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei willkürlich im Sinne von <ref-law> (<ref-ruling> E. 2 S. 117 mit Hinweis). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>). Die Partei, welche die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substantiiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 1.3.1 S. 18 mit Hinweisen).
Wer geltend macht, die Vorinstanz habe durch eine unvollständige Sachverhaltsfeststellung eine Norm des materiellen Rechts verletzt, und deshalb den Sachverhalt ergänzen will, hat mit Aktenhinweisen darzulegen, dass er entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den kantonalen Instanzen prozesskonform eingebracht hat, andernfalls die behaupteten Tatsachen als neu zu qualifizieren sind (<ref-ruling> E. 2 S. 90 mit Hinweisen). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>), was in der Beschwerde näher darzulegen ist (<ref-ruling> E. 3 S. 395).
2.3. Macht die beschwerdeführende Partei eine Verletzung des Willkürverbots geltend, genügt es nicht, wenn sie bloss ihre eigene Darstellung derjenigen der Vorinstanz gegenüberstellt und behauptet, der angefochtene Entscheid sei willkürlich (<ref-ruling> E. 3 S. 352 mit Hinweisen). Sie hat vielmehr im Einzelnen anhand der Erwägungen des angefochtenen Entscheids darzulegen, inwiefern dieser an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.3 S. 60; <ref-ruling> E. 1.2 S. 234; je mit Hinweisen). Willkür liegt dabei nicht schon vor, wenn eine andere Lösung ebenfalls in Betracht zu ziehen oder gar vorzuziehen wäre, sondern nur, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Der angefochtene Entscheid ist dabei nur aufzuheben, wenn er auch im Ergebnis und nicht nur in der Begründung verfassungswidrig ist (<ref-ruling> E. 2.1 S. 18 f.; <ref-ruling> E. 3.2.5 S. 339; je mit Hinweisen).
Die Beweiswürdigung erweist sich als willkürlich, wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt hat, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen hat oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat (<ref-ruling> E. 4.2 S. 234 mit Hinweisen). Allein dass die vom Gericht gezogenen Schlüsse nicht mit der Darstellung der beschwerdeführenden Partei übereinstimmen, belegt noch keine Willkür (<ref-ruling> E. 2.3 S. 266 mit Hinweisen). Entsprechend genügt es nicht, lediglich einzelne Beweise anzuführen, die anders als im angefochtenen Entscheid gewichtet werden sollen, und dem Bundesgericht in appellatorischer Kritik die eigene Auffassung zu unterbreiten, als ob diesem eine freie Sachverhaltsprüfung zukäme (vgl. U rteil 4A_606/2015 vom 19. April 2016 E. 2.1).
3.
Sowohl die Sorgfaltspflichtverletzung des Beschwerdegegners - er vergewisserte sich nicht, ob der Beschwerdeführer den Vorschuss aufforderungsgemäss geleistet hat - als auch sein Verschulden waren vor der Vorinstanz unbestritten. Strittig sind hingegen der Kausalzusammenhang (nachfolgend E. 4) sowie der Schaden (nachfolgend E. 5).
4.
4.1. Bei einer Unterlassung bestimmt sich der Kausalzusammenhang danach, ob der Schaden auch bei Vornahme der unterlassenen Handlung eingetreten wäre. Es geht um einen hypothetischen Kausalverlauf, für den nach den Erfahrungen des Lebens und dem gewöhnlichen Lauf der Dinge eine überwiegende Wahrscheinlichkeit sprechen muss (<ref-ruling> E. 3d S. 165 mit Hinweis). Grundsätzlich unterscheidet die Rechtsprechung auch bei Unterlassungen zwischen natürlichem und adäquatem Kausalzusammenhang. Während bei Handlungen die wertenden Gesichtspunkte erst bei der Beurteilung der Adäquanz zum Tragen kommen, spielen diese Gesichtspunkte bei Unterlassungen in der Regel schon bei der Feststellung des hypothetischen Kausalverlaufs eine Rolle. Es ist daher bei Unterlassungen in der Regel nicht sinnvoll, den festgestellten oder angenommenen hypothetischen Geschehensablauf auch noch auf seine Adäquanz zu prüfen. Die Feststellungen des Sachrichters im Zusammenhang mit Unterlassungen sind daher entsprechend der allgemeinen Regel über die Verbindlichkeit der Feststellungen zum natürlichen Kausalzusammenhang für das Bundesgericht bindend; nur wenn die hypothetische Kausalität ausschliesslich gestützt auf die allgemeine Lebenserfahrung festgestellt wird, unterliegt sie der freien Überprüfung durch das Bundesgericht (<ref-ruling> E. 2.3 S. 718 f.; Urteile 4A_577/2015 vom 1. März 2016 E. 7.1; 4A_588/2011 vom 3. Mai 2012 E. 2.2.2; je mit Hinweisen).
4.2. Der geltend gemachte Schaden - im Wesentlichen der Wegfall des in der Schweiz künftig Ersparten - hängt direkt mit der Ausweisung des Beschwerdeführers zusammen, welche wiederum mit dem (hypothetischen) Ausgang des Verfahrens vor dem Verwaltungsgericht des Kantons Luzern in Verbindung steht. Die Vorinstanz ging implizit davon aus, der Beschwerdeführer hätte den Kostenvorschuss fristgerecht bezahlt, wenn er vom Beschwerdegegner nach dessen Kontrolle erneut dazu aufgefordert worden wäre. Das Verwaltungsgericht hätte alsdann die Beschwerde materiell beurteilt. Aufgrund der vorhandenen Indizien erachtete es die Vorinstanz als überwiegend wahrscheinlich, dass das Verwaltungsgericht die Beschwerde abgewiesen, also die Aufenthaltsbewilligung des Beschwerdeführers nicht verlängert hätte. Beim erwarteten Prozessausgang sei die Ausweisung des Beschwerdeführers nicht auf die Unterlassung des Beschwerdegegners zurückzuführen; vielmehr wäre sie so oder so erfolgt, allerdings erst nach erschöpftem Instanzenzug. Ohne Pflichtverletzung hätte der Beschwerdeführer daher während 19 weiterer Monate - zwischen der tatsächlichen Ausweisung und dem hypothetischen Ausweisungszeitpunkt nach erschöpftem Instanzenzug - durch Ausübung einer Erwerbstätigkeit in der Schweiz noch eine Sparquote erzielt; insofern bestehe ein hypothetischer Kausalzusammenhang zwischen Pflichtverletzung und Schaden. Für die Zeit danach sei ein solcher aufgrund des präsumtiven Verfahrensausgangs hingegen nicht gegeben.
Damit hat die Vorinstanz die hypothetische Kausalität nicht gestützt auf die allgemeine Lebenserfahrung ermittelt, sondern anhand von konkreten Sachverhaltsfeststellungen. Einer freien Überprüfung durch das Bundesgericht sind diese Feststellungen nicht zugänglich (vgl. E. 4.1 hiervor).
4.3. Der Beschwerdeführer macht zunächst eine Verletzung von <ref-law> durch eine unzutreffende Verteilung der Beweislast geltend. Die Vorinstanz gehe zu Recht davon aus, er trage die Beweislast für den hypothetischen Kausalzusammenhang, halte aber zugleich zutreffend fest, im fraglichen Verwaltungsgerichtsverfahren hätte die Behörde den Rechtsmissbrauch zu beweisen gehabt, woran hohe Anforderungen zu stellen seien. Dies beachte die Vorinstanz bei der Beurteilung des präsumtiven Verfahrensausgangs jedoch nicht; vielmehr dränge sie ihn, den Beschwerdeführer, in die Beweisrolle.
Die Vorinstanz kommt zum Schluss, mit überwiegender Wahrscheinlichkeit - dem insofern unstreitig zur Anwendung gelangenden Beweismass - hätte das Verwaltungsgericht die Beschwerde abgewiesen. Betreffend den hypothetischen Kausalzusammenhang und insbesondere den präsumtiven Verfahrensausgang liegt somit kein offenes Beweisergebnis vor. Die Beweislastverteilung ist daher gegenstandslos (<ref-ruling> E. 4.3.4 S. 241; <ref-ruling> E. 5.4 S. 602) und die Berufung auf <ref-law> stösst ins Leere.
4.4. Eine weitere Verletzung von <ref-law> sieht der Beschwerdeführer darin, dass die Vorinstanz seinen Beweisantrag auf Parteibefragung bzw. Beweisaussage ablehnte mit der Begründung, er sei bereits von verschiedenen Behörden ausführlich befragt worden, weshalb nicht ersichtlich sei, inwiefern er zu den gleichen Umständen zu einem späteren Zeitpunkt schlüssige Beweise sollte liefern können. Zudem gebe er nicht an, für welche Behauptungen diese Einvernahme Beweis erbringen solle. Dagegen wendet der Beschwerdeführer ein, er sei bisher noch nie unter Strafandrohung bei Falschaussage befragt worden, was das Verwaltungsgericht jedoch hätte tun können und wodurch seinen Ausführungen ein ganz anderer und weit höherer Stellenwert zugekommen wäre. Zudem hätte das Verwaltungsgericht dadurch einen persönlichen Eindruck von ihm gewinnen können. Die Vorinstanz gehe davon aus, aufgrund des Untersuchungsgrundsatzes hätte das Verwaltungsgericht die beantragten Zeugen einvernommen, erläutere aber gleichzeitig nicht, weshalb es von einer Parteibefragung abgesehen hätte. Das Beweisthema, zu welchem die Parteibefragung hätte Beweis erbringen sollen, formuliere sich hier von selbst; der Beschwerdeführer wäre zur Scheinehe bzw. zum Festhalten an einer inhaltsleeren Ehe zu befragen gewesen. Da die Behörde beweispflichtig gewesen wäre, hätte diese die einzelnen Fragen formulieren müssen.
Das Bundesgericht greift in eine antizipierte Beweiswürdigung nur ein, wenn sie willkürlich ist (<ref-ruling> E. 4.3.2 S. 376 mit Hinweis; siehe zur Willkür E. 2.3 hiervor). Die Vorinstanz verzichtete auf eine Parteibefragung, weil der Beschwerdeführer bereits mehrmals befragt wurde und sie deshalb von einer eigenen Befragung keine neuen Beweise erwartete. Welche zusätzlichen Erkenntnisse durch eine weitere Befragung hätten erlangt werden können, liegt nicht auf der Hand und wird vom Beschwerdeführer auch nicht erläutert, womit es an einer Auseinandersetzung mit der vorinstanzlichen Argumentation fehlt. Die pauschale Behauptung, eine Aussage unter Strafandrohung hätte einen ganz anderen und weit höheren Stellenwert gehabt, genügt nicht, um die diesbezügliche antizipierte Beweiswürdigung als willkürlich dazutun.
Im Übrigen vermengt der Beschwerdeführer die im Zivilprozess geltenden Verfahrensgrundsätze mit den im Verwaltungsverfahren zur Anwendung gelangenden. Auch wenn es bei der Feststellung des hypothetischen Kausalzusammenhangs den Ausgang des verwaltungsgerichtlichen Verfahrens zu antizipieren gilt, handelt es sich dennoch unverändert um einen Zivilprozess und die im verwaltungsrechtlichen Verfahren massgebliche Untersuchungsmaxime schlägt nicht gleichsam darauf durch. Die Beweisführungslast fällt im vorliegenden, von der Verhandlungsmaxime beherrschten Zivilverfahren der einen oder der anderen Partei zu; einem am Verfahren nicht beteiligten Dritten kann sie ebenso wenig zugeschoben werden wie es Sache dieses Dritten sein kann, im Rahmen einer Parteibefragung Fragen zu formulieren. Wie die Vorinstanz zutreffend festhielt, ist ein Beweismittel in diesem Verfahren nur dann formgerecht anerboten, wenn sich die Beweisofferte eindeutig einer damit zu beweisenden Tatsachenbehauptung zuordnen lässt und umgekehrt (Urteile 4A_56/2013 vom 4. Juni 2013 E. 4.4; 4A_283/2012 vom 31. Juli 2012 E. 5.3). Der Beschwerdeführer gibt in seiner Beschwerde nicht mit Aktenhinweisen an (vgl. E. 2.2 hiervor), bezüglich welcher Tatsachenbehauptungen er dieses Beweismittel im kantonalen Verfahren angerufen hat; er begnügt sich mit dem Vorbringen, das Beweisthema Scheinehe formuliere sich hier von selbst. Dem ist bereits deshalb nicht so, weil unter anderem auch der Schaden umstritten ist (vgl. E. 3 hiervor). Indem der Beschwerdeführer eine generelle Parteibefragung beantragte ohne zu präzisieren, zu welchen Tatsachenbehauptungen diese durchzuführen wäre, vermochte er den zivilprozessualen Anforderungen nicht gerecht zu werden. Auch aus diesem Grund war die Vorinstanz nicht gehalten, dieses Beweismittel abzunehmen.
4.5. Des Weiteren macht der Beschwerdeführer eine willkürliche Beweiswürdigung geltend. Allerdings beschränkt er sich dabei teilweise darauf, der vorinstanzlichen Würdigung seine eigene gegenüber zu stellen und diejenige der Vorinstanz als willkürlich zu bezeichnen (so etwa bezüglich der Kinder, die beide Ehegatten während ihrer Fernbeziehung je mit einem anderen Partner gezeugt haben, der Würdigung der Aussagen seiner Neffen und seines Bruders oder der eingereichten Fotos der Ehegatten). Den Anforderungen an eine Willkürrüge ist damit nicht Genüge getan; auf solch appellatorische Kritik ist von vornherein nicht einzugehen.
4.5.1. Die Vorinstanz erachtete es als überwiegend wahrscheinlich, dass das Verwaltungsgericht von einer Scheinehe ausgegangen wäre und die Beschwerde abgewiesen hätte. Sie hielt fest, es könne zwar nicht ausgeschlossen werden, dass C._ die Ehe tatsächlich mit dem Willen auf Gründung einer Lebensgemeinschaft eingegangen sei. Es genüge aber, wenn der ausländische Ehegatte die Ehe einzig aus ausländerrechtlichen Motiven geschlossen und keine Lebensgemeinschaft angestrebt habe. Die vorhandenen Indizien würden in ihrer Gesamtheit zum Ergebnis führen, dass der Beschwerdeführer die Ehe primär zum Zweck geschlossen habe, eine Aufenthaltsbewilligung zu erlangen; dafür, dass er mit seiner Schweizer Ehegattin eine Lebensgemeinschaft habe aufbauen wollen, die diese Bezeichnung auch verdiene, fänden sich keine ausreichenden Anhaltspunkte. Auch sei nicht ersichtlich, dass diese ursprünglich missbräuchliche Absicht von einer gegenseitigen Zuneigung und dem Wunsch nach Zusammenleben abgelöst und die Ehe im Laufe der Zeit tatsächlich gelebt worden wäre. Als relevante Indizien, die gegen einen Willen des Beschwerdeführers zur Bildung einer Lebensgemeinschaft sprechen würden, führte die Vorinstanz zusammengefasst insbesondere folgende auf: Die Umstände der Bekanntschaft, bestehend aus dem losen Kontakt während vier Jahren nach dem ersten, zufälligen Treffen in der Schweiz, ohne dass ein weiteres persönliches Treffen stattgefunden hätte; die plötzliche Heirat in Mazedonien ohne Anwesenheit des Freundes- oder Familienkreises und die Rückreise der Ehefrau in die Schweiz nach nur wenigen Tagen; die Inkohärenzen in den Befragungen, vor allem bezüglich der Hochzeitsfeierlichkeiten und der Einreiseformalitäten; die spärlichen Kenntnisse über die Vergangenheit und das Leben des anderen Ehegatten sowie das Fehlen einer Wohngemeinschaft während mehrerer Jahre bzw. die späte Aufnahme einer solchen zur Sicherung der Aufenthaltsbewilligung.
4.5.2. Der Beschwerdeführer rügt als stossend, wenn die Vorinstanz wegen der Art des Kennenlernens Zweifel am Willen für eine Lebensgemeinschaft hege, wobei sie ausserdem willkürlich unterschlage, dass sich die Eheleute bereits 1999/2000 in der Schweiz kennengelernt hätten.
Die Vorinstanz legte im Einzelnen dar, weshalb gerade auch aufgrund der sprachlichen Barriere zwischen den Ehegatten fraglich sei, wie gut sich diese vor der Eheschliessung kannten, zumal abgesehen vom Kennenlernen im Dezember 1999 und Januar 2000 in der Schweiz bloss telefonischer Kontakt zwischen ihnen bestanden habe. Dies werfe erste Zweifel hinsichtlich der hinter der Heirat stehenden Motivation auf. Inwiefern diese Beweiswürdigung willkürlich sein soll, legt der Beschwerdeführer nicht dar und ist auch nicht ersichtlich. Dass die Umstände des Kennenlernens Indizien für eine Scheinehe sein können, ergibt sich aus der bundesgerichtlichen Rechtsprechung (vgl. nur Urteil 2C_740/2015 vom 10. Februar 2016 E. 3.2 mit Hinweis); dasselbe gilt für Schwierigkeiten in der Kommunikation (Urteil 5A_30/2014 vom 15. April 2014 E. 3.3).
4.5.3. Weiter beruft sich der Beschwerdeführer darauf, das Alkoholproblem von C._ sei für ihre teils verwirrenden Aussagen verantwortlich. Die Vorinstanz habe dies aber nicht ernst genommen bzw. als Ausrede des Beschwerdeführers qualifiziert.
Die Vorinstanz ging davon aus, der übermässige Alkoholkonsum von C._ habe rund drei Jahre nach der Eheschliessung begonnen. Die Aussagen von ihr und insbesondere die "Lücken" darin (z.B. Nichtwissen des Geburtsdatums des Ehemanns, seiner Ausbildung, seines im Heimatland ausgeübten Berufs und der Vornamen seiner Familienangehörigen, bei welchen C._ sehr gut integriert gewesen sein soll) liessen sich aber nicht damit erklären. Die Vorinstanz hielt es für kaum vorstellbar, dass innert so kurzer Zeit derart gedächtnisvermindernde Auswirkungen durch den Alkoholkonsum eingetreten sein sollen, insbesondere da C._ über bestimmte andere Vorgänge genau Auskunft geben könne. Im Übrigen vermöge auch der Beschwerdeführer, der nicht unter einem Alkoholabusus leide, nur wenig über den Alltag seiner Ehefrau zu berichten. Die Vorinstanz hat den Alkoholkonsum von C._ demnach in ihre Betrachtung mit einbezogen, ihm aber nicht dieselbe Bedeutung zugemessen wie der Beschwerdeführer es tut. Mit der vorinstanzlichen Argumentation setzt sich der Beschwerdeführer nicht auseinander und inwiefern deren Wertung willkürlich sein soll, legt er nicht dar. Stattdessen nimmt er eine andere Gewichtung der Aussagen von C._ vor, womit er den Anforderungen an eine Willkürrüge nicht genügt (vgl. E. 2.3 hiervor). Dass fehlende Kenntnisse über den Ehegatten auf eine Scheinehe hinweisen können, stimmt mit der bundesgerichtlichen Rechtsprechung überein (vgl. etwa zit. Urteil 5A_30/2014 E. 3.3).
4.5.4. Der Beschwerdeführer macht geltend, die Vorinstanz lasse völlig ausser Acht, dass er für den Unterhalt von C._ und deren Tochter aufgekommen sei, was jeglichem Anschein einer Scheinehe widerspreche.
Dass d.er Beschwerdeführer C._ und deren Tochter finanziell unterstützte, hat die Vorinstanz entgegen der Darstellung des Beschwerdeführers berücksichtigt. Ihres Erachtens lässt sich daraus nicht auf die Führung eines Ehelebens schliessen, sondern bilden diese Beträge einzig die Grundlage für eine zumindest formelle Aufrechterhaltung der Ehe mit der nicht erwerbstätigen Ehefrau. Mit diesem Argument setzt sich der Beschwerdeführer nicht auseinander. Willkür ist bereits deshalb nicht dargetan.
4.5.5. Willkürlich sei sodann, dass die Vorinstanz die getrennten Wohnorte der Ehegatten als Indiz für eine fehlende Lebensgemeinschaft und damit für eine Scheinehe betrachtet habe. Der Beschwerdeführer habe dank der Beziehungen seiner Brüder eine Anstellung im Kanton Graubünden gefunden, weshalb er wegen der Distanz nicht zu seiner Frau in den Kanton Luzern habe ziehen können. Dass seine Frau nicht zu ihm habe ziehen wollen, liege an ihrer Eigenwilligkeit, welche ihm nicht angelastet werden könne, andernfalls er der Willkür seiner schweizerischen Ehefrau ausgeliefert wäre. Er habe sich um ein Zusammenwohnen bemüht, einerseits durch Überreden seiner Ehefrau zu einem Umzug in den Kanton Graubünden, andererseits durch die Suche nach einer Arbeitsstelle für sich in der Zentralschweiz.
Die Vorinstanz hielt fest, ein Zusammenleben der Ehegatten sei zwar keine Bewilligungsvoraussetzung und eheliche Beziehungen könnten auch in getrennten Haushalten gepflegt werden, etwa wenn bei intakter Ehe aus beruflichen oder anderen Gründen kein gemeinsamer Haushalt geführt werde. Gleichwohl erachtete sie die Tatsache, dass die Ehegatten seit der Einreise des Beschwerdeführers in die Schweiz während fast fünf Jahren keine eigentliche Wohngemeinschaft aufnahmen, als gewichtiges Indiz gegen einen Willen des Beschwerdeführers auf Bildung einer Lebensgemeinschaft und damit für eine Scheinehe, was im Einklang mit der bundesgerichtlichen Rechtsprechung steht (<ref-ruling> E. 2b S. 295; Urteil 2C_1033/2014 vom 29. April 2015 E. 2.2). Sie stellte fest, der Beschwerdeführer habe nicht aktiv versucht, der getrennten Wohnsituation entgegenzuwirken. Für eine Stelle im Kanton Luzern habe er sich während dieser Zeit nie beworben und erst nach der Trennung der Ehegatten [und nachdem ihm von der zuständigen Behörde ein Wochenaufenthalt im Kanton Graubünden untersagt wurde] habe er eine Stelle im Kanton Nidwalden angetreten. Der erstmalige Zusammenzug der Ehegatten in U._, Kanton Graubünden, sei im Juli 2008 erfolgt, kurz nachdem die Kantonspolizei im April 2008 im Auftrag des AfM Luzern die Wohnung von C._ im Kanton Luzern besichtigt habe; seit Anfang des Jahres 2009 lebten die Ehegatten wieder getrennt. Relevant sei diesbezüglich auch die Aussage von C._, wonach der Beschwerdeführer sie nach der polizeilichen Abklärung überredet habe, nach U._ zu ziehen, um zu verhindern, dass ihm der "Ausweis" entzogen werde.
Mit diesen Erwägungen setzt sich der Beschwerdeführer kaum auseinander. Vielmehr ergänzt er zum einen den Sachverhalt, ohne mit Aktenhinweisen darzulegen, dass er die entsprechenden Tatsachen bereits bei den kantonalen Gerichteneingebracht hat (so etwa bezüglich der Tatsache, dass er C._ schon seit Beginn ihrer Ehe von einem Umzug in den Kanton Graubünden zu überreden versucht habe). Zum anderen stellt er seine eigene Darstellung derjenigen der Vorinstanz gegenüber, ohne dabei darzutun, inwiefern die vorinstanzliche Auffassung offensichtlich unrichtig sein soll (so etwa bezüglich der Tatsache, dass er in der Zentralschweiz eine Arbeitsstelle gesucht habe). Den Anforderungen an Willkürrügen (vgl. E. 2.3 hiervor) genügt dies nicht, weshalb nicht weiter darauf einzugehen ist.
4.5.6. Der Schluss auf eine Scheinehe sei vor allem auch deshalb willkürlich, weil sich die Ehegatten immer an den Wochenenden getroffen hätten. Selbst wenn ursprünglich kein echter Wunsch nach Zusammenleben bestanden hätte, wäre dies durch die im Laufe der Zeit tatsächlich gelebte Ehe - insbesondere eben durch die Wochenendbesuche - geheilt worden. Die Vorinstanz fokussiere darauf, wie intensiv die Ehegatten diese Wochenenden zusammen verbracht hätten. Das sei jedoch nicht relevant. Entscheidend sei allein die Tatsache, dass sie an den Wochenenden zueinander gefunden hätten. Die häufigen Besuche des Beschwerdeführers bei C._ würden auch durch die Aussagen einer Nachbarin sowie seiner Neffen bestätigt.
Die Vorinstanz stellte fest, dass sich die Ehegatten während der Zeit der getrennten Wohnorte an den Wochenenden getroffen haben. Sie liess allerdings offen, wie häufig dies der Fall war und hielt nur fest, gemäss Angaben des Beschwerdeführers sei er etwa drei Mal im Monat bei C._ gewesen. Die Häufigkeit dieser Wochenendbesuche war für die Vorinstanz nicht ausschlaggebend, da sie auf deren "Gehalt" abstellte. Insofern fiel die Aussage von C._ ins Gewicht, wonach sie auch an diesen Wochenenden allein zu Hause gewesen sei, da der Beschwerdeführer seine Schwester in V._ besucht und mit dieser seine Zeit verbracht habe. In die Ferien nach Mazedonien habe er sie nie mitgenommen und kein einziges Weihnachtsfest habe er mit ihr verbracht. Zudem stellte die Polizei anlässlich der Besichtigung der Wohnung von C._ fest, es seien wenig bis gar keine Männerkleider und vor allem im Badezimmer keine auf die Anwesenheit einer zweiten Person hindeutenden Utensilien gefunden worden.
Massgebend ist, ob sich in den Wochenendbesuchen ein Wille der Ehegatten, insbesondere des Beschwerdeführers, zur Bildung einer Lebensgemeinschaft manifestiert oder nicht (vgl. auch Urteil 2C_183/2013 vom 1. Juli 2013 E. 1.5, wonach nicht die Wohnverhältnisse allein massgeblich sind, sondern die ehelichen Verhältnisse). Grundsätzlich zu Recht stellte die Vorinstanz daher nicht auf die bloss äussere Tatsache der erfolgten Wochenendbesuche ab, sondern darauf, dass die Ehegatten an diesen Wochenenden dennoch keine oder nur wenig Zeit gemeinsam verbrachten. Wenn die Vorinstanz aus den Wochenendbesuchen aufgrund deren Ausgestaltung ohne Abklärung ihrer Häufigkeit auf einen fehlenden (und nicht etwa einen bestehenden) Willen des Beschwerdeführers zur Bildung einer Lebensgemeinschaft schloss, ist dies nicht willkürlich.
Ähnlich verhält es sich mit der in der gemeinsamen Wohnung (Juli 2008 bis Anfang 2009) verbrachten Zeit, hinsichtlich der für das Bundesgericht verbindlich festgestellt ist, dass der Beschwerdeführer zwar sehr oft dort zum Abendessen war, jedoch jeweils nach dem Essen zu seinem Bruder nach W._ fuhr. Dem Beschwerdeführer ist zuzustimmen, dass es für eine gelebte Ehe nicht darauf ankommen kann, ob er nun jeden Abend oder "bloss" häufig in der gemeinsamen Wohnung war. Auf einen fehlenden Willen zur Bildung einer Lebensgemeinschaft schloss die Vorinstanz aber primär deshalb, weil der Beschwerdeführer die gemeinsame Wohnung nach dem Abendessen jeweils wieder verliess und kaum bei seiner Ehefrau war. Der Beschwerdeführer erklärt seine Abwesenheit mit dem Alkoholkonsum von C._; er habe durch die Besuche bei seinen Verwandten Streitigkeiten mit ihr aus dem Weg gehen wollen. Diese Erklärung erscheint zwar bis zu einem gewissen Grad verständlich, zeigt aber gleichzeitig, dass der Beschwerdeführer seiner Ehefrau auswich und die Zeit möglichst nicht mit ihr verbrachte, was umso mehr ins Gewicht fällt, wenn man sich vor Augen führt, dass die Ehegatten nunmehr nach fünf Jahren Ehe zum ersten Mal eine gemeinsame Wohnung hatten. Dass die vorinstanzliche Sachverhaltsfeststellung bezüglich des fehlenden inneren Willens des Beschwerdeführers zur Bildung einer Lebensgemeinschaft willkürlich wäre, ist mit dieser Begründung der Abwesenheit jedenfalls noch nicht dargetan.
4.5.7. Eine willkürliche Beweiswürdigung durch die Vorinstanz bezüglich Scheinehe resp. fehlender später tatsächlich gelebter Ehe ist nicht dargetan, soweit überhaupt genügende Willkürrügen vorliegen. Es ist daher von den vorinstanzlichen Feststellungen zum hypothetischen Kausalverlauf (vgl. E. 4.2 hiervor) auszugehen und auf diese abzustellen.
Bei diesem Ergebnis erübrigt sich eine Prüfung der Willkürrügen gegen die von der Vorinstanz festgestellte missbräuchliche Berufung auf eine bloss noch formell bestehende Ehe, welche die Vorinstanz als alternativen Grund für die überwiegend wahrscheinliche Abweisung der Verwaltungsgerichtsbeschwerde anführte.
5.
Soweit der Beschwerdeführer eine Genugtuung beansprucht, geht er von einem anderen Beweisergebnis aus, namentlich von einer hypothetischen Gutheissung der Beschwerde durch das Verwaltungsgericht. Auf seine diesbezüglichen Ausführungen ist nicht einzugehen.
Zu behandeln bleibt die Höhe des Schadens, welcher daraus entstanden ist, dass der Beschwerdeführer aufgrund der Pflichtverletzung des Beschwerdegegners 19 Monate früher aus der Schweiz ausgewiesen wurde (vgl. E. 4.2 hiervor). Bereits vor der Vorinstanz war unbestritten, dass dieser Schaden der Sparquote entspricht, die der Beschwerdeführer in der Schweiz erzielt hätte. Ebenfalls unbestritten war die Ansicht des Bezirksgerichts, dieser Schaden sei nicht ziffernmässig nachweisbar, weshalb es ihn gestützt auf <ref-law> schätzte. Diese Punkte werden im bundesgerichtlichen Verfahren nicht gerügt und der Entscheid braucht insofern nicht überprüft zu werden (vgl. E. 2.1 hiervor).
Der Beschwerdeführer wendet sich in seiner Beschwerde gegen zwei von den kantonalen Gerichten bei der Schadensschätzung nach <ref-law> berücksichtigte Ausgabenpositionen; zum einen die Anwalts- und Gerichtskosten für das Verfahren vor dem Verwaltungs- und dem Bundesgericht, zum anderen die Fahrkosten für die Verwandtenbesuche. Auf die Anwalts- und Gerichtskosten ist nicht weiter einzugehen, da der Beschwerdeführer insofern wie bezüglich der Genugtuung von einem anderen Beweisergebnis ausgeht. Bezüglich der Fahrkosten macht er einerseits geltend, deren Berücksichtigung verstosse gegen die Verhandlungsmaxime und die Beweislastverteilung, da der Beschwerdegegner diese Position weder behauptet noch - als anspruchsmindernde Tatsache - bewiesen habe. Andererseits sei sowohl die Anzahl angenommener Besuche von 28 pro Jahr als auch der angerechnete Kilometerpreis von einem Franken übersetzt.
5.1. Schaden ist die ungewollte Verminderung des Reinvermögens, die in einer Verminderung der Aktiven, einer Vermehrung der Passiven oder in entgangenem Gewinn bestehen kann. Der Schaden entspricht der Differenz zwischen dem gegenwärtigen Vermögensstand und dem Stand, den das Vermögen ohne das schädigende Ereignis hätte (<ref-ruling> E. 8.1.1 S. 187 f. mit Hinweisen).
Der Beschwerdeführer macht als Schaden den entgangenen Vermögenszuwachs geltend, den er erzielt hätte, wenn er während 19 weiterer Monate in der Schweiz verblieben wäre. Dies entspricht der kumulierten Sparquote, die aus seinem Nettoeinkommen abzüglich seiner hiesigen Lebenshaltungskosten resultiert wäre. Für den Schaden - hier eben die Sparquote - trägt der Beschwerdeführer die Beweislast; um Schadenminderung geht es dabei nicht.
Ebenso wenig ist etwas dagegen einzuwenden, dass die kantonalen Gerichte die Kosten für die Verwandtenbesuche bei der Schadensermittlung berücksichtigten, obwohl der Beschwerdegegner sie nicht behauptete. Denn erstens oblag es dem Beschwerdeführer und nicht dem Beschwerdegegner, die für die Schadensschätzung nach <ref-law> erforderlichen tatsächlichen Grundlagen zu behaupten (vgl. Urteil 4A_364/2013 vom 5. März 2014 E. 9.3 mit Hinweis), woz u wie ausgeführt auch die Lebenshaltungskosten in der Schweiz gehören. Und zweitens gehört es geradezu zum Wesen der ermessensweisen Schadensschätzung, dass das Gericht "mit Rücksicht auf den gewöhnlichen Lauf der Dinge" gestützt auf den erwiesenen Sachverhalt - die enge familiäre Bindung und die in der Vergangenheit erfolgten Verwandtenbesuche - in einem gewissen Ausmass eigene Annahmen über die künftige Entwicklung trifft resp. treffen muss, um eben den Schaden schätzen zu können (vgl. auch <ref-ruling> E. 3.7.2.2 S. 339 mit Hinweisen).
5.2. Die Schadensschätzung gestützt auf <ref-law> beruht - von der ausnahmsweisen Berücksichtigung abstrakter Erfahrungssätze abgesehen - auf Tatbestandsermessen. Damit gehört sie zur Sachverhaltsfeststellung und ist vom Bundesgericht nur auf Willkür überprüfbar (<ref-ruling> E. 5.1 S. 364 mit Hinweis).
Die appellatorische Kritik des Beschwerdeführers, wonach die Anzahl angenommener Verwandtenbesuche ebenso wie die Höhe der Fahrkosten übersetzt seien, vermag den Anforderungen an eine Willkürrüge nicht zu genügen. Selbst wenn, wäre damit nicht dargetan, dass die kantonalen Gerichte ihr Tatbestandsermessen offensichtlich unrichtig ausgeübt hätten, zumal bei einer Schadensschätzung nach <ref-law> ohnehin eine gewisse Schematisierung zulässig ist (vgl. zit. Urteil 4A_364/2013 E. 10.1).
6.
Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Da der Beschwerdeführer primär eine Verletzung des Willkürverbots geltend macht, aber entweder die diesbezüglichen Begründungsanforderungen nicht erfüllt oder keine Willkür vorliegt, ist die Beschwerde in Anbetracht ihrer geringen Erfolgsaussichten als von vornherein aussichtslos zu qualifizieren D as Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege für das Verfahren vor Bundesgericht ist daher ebenfalls abzuweisen (<ref-law>).
Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kostenpflichtig (<ref-law>). Eine Parteientschädigung an den Beschwerdegegner hat er nicht zu leisten, da diesem keine notwendigen Kosten im Sinne von <ref-law> entstanden sind. Das Gesuch um Sicherstellung der Parteikosten reichte der Beschwerdegegner bereits nach Erhalt der Eingangsanzeige ein, obwohl in diesem Zeitpunkt noch ungewiss war, ob ihn das Gericht überhaupt zur Einreichung einer Vernehmlassung einladen wird oder nicht. Bedarf, das Gesuch um Sicherstellung schon in diesem Verfahrensstadium zu stellen, bestand nicht. Vielmehr hätte es genügt, dieses nach erfolgter Einladung zur Stellungnahme einzureichen, verbunden mit einem Antrag auf Abnahme der richterlichen - und damit erstreckbaren - Frist zur Stellungnahme gemäss <ref-law> (vgl. auch GEISER/UHLMANN, Grundlagen, in: Prozessieren vor Bundesgericht, 4. Aufl. 2014, S. 35 Rz. 1.71; zum Vorgehen bei einer Berufung nach ZPO siehe <ref-ruling> E. 2.5.2 S. 558 f.). Das Gericht sah von der Einholung einer Vernehmlassung ab, weshalb sich die Kosten des frühzeitig gestellten Gesuchs um Sicherstellung der Parteikosten als nicht notwendig erwiesen haben. Kosten für eine Stellungnahme sind dem Beschwerdegegner mangels Einholung einer solchen von vornherein nicht erwachsen.
Für die dem Beschwerdegegner bei Einreichung des Sicherstellungsgesuchs bereits entstandenen Kosten, hier die Kosten für die Redaktion ebendieses Gesuchs, erweist sich das Gesuch um Sicherstellung als gegenstandslos (vgl. <ref-ruling> E. 2 S. 88 mit Hinweis). Abgesehen davon sind diese Kosten, wie ausgeführt, nicht zu entschädigen und auch aus diesem Grund nicht sicherzustellen. Und für dem Beschwerdegegner nicht erwachsene Kosten, hier durch Nichteinholung einer Vernehmlassung, ist praxisgemäss keine Parteient-schädigung zuzusprechen, weshalb das Sicherstellungsgesuch auch diesbezüglich als gegenstandslos abzuschreiben ist (vgl. Urteil 5C.158/2006 vom 23. März 2007 E. 8, nicht publ. in: <ref-ruling>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch des Beschwerdeführers um Gewährung der unentgeltlichen Rechtspflege für das bundesgerichtliche Verfahren wird abgewiesen.
3.
Die Gerichtskosten von Fr. 5'000.-- werden dem Beschwerdeführer auferlegt.
4.
Es werden keine Parteikosten zugesprochen.
5.
Das Gesuch des Beschwerdegegners um Sicherstellung der Parteikosten wird als gegenstandslos abgeschrieben.
6.
Dieses Urteil wird den Parteien und dem Kantonsgericht von Graubünden, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 9. Juni 2016
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Lüthi