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.