Auftrag; Sorgfaltspflicht, hat sich ergeben:
A.-Aufgrund eines Strafverfahrens wegen Widerhandlung gegen das Betäubungsmittelgesetz befand sich der Kläger in der Zeit vom 27. Juni 1988 bis zum 13. April 1989 in den Niederlanden in Auslieferungs- und anschliessend bis
15. Juni 1989 in Arlesheim/BL in Untersuchungshaft. Die gesamte Haftzeit betrug 353 Tage. Mit Urteil des Strafgerichts des Kantons Basel-Landschaft vom 4. September 1991 wurde der Kläger freigesprochen, worauf er Schadenersatz- und Genugtuungsansprüche geltend machte. Nach Abweisung der Klage durch das Strafgericht Basel-Landschaft, sprach das Obergericht des Kantons Basel-Landschaft mit Beschluss vom 15. Dezember 1992 dem Kläger für Anwaltskosten Fr. 32'784. 60 nebst Zins und Fr. 5'000.-- nebst Zins als Genugtuung zu, während seine gestützt auf Verdienstausfall und weitergehenden Schaden geltend gemachte Forderung abgewiesen wurde.
Eine dagegen erhobene staatsrechtliche Beschwerde hiess das Bundesgericht mit Urteil vom 6. April 1994 einzig bezüglich der Höhe der Genugtuung gut, worauf das Obergericht BL die Genugtuung auf Fr. 10'000.-- erhöhte.
Daraufhin beauftragte der Kläger den Beklagten, die Forderung aus Verdienstausfall und sonstigen materiellen Nachteilen, verursacht durch die erlittene Haft, gegenüber dem Kanton Basel-Landschaft im Rahmen einer Staatshaftungsklage geltend zu machen. Das Friedensrichteramt Liestal stellte am 23. Mai 1994 den entsprechenden Akzessschein aus.
In seiner Funktion als Anwalt des Klägers versäumte der Beklagte indessen die einjährige Frist zur Einreichung der Klage, so dass die Ansprüche des Klägers gegenüber dem Kanton verwirkten.
B.- Mit Klage vom 31. Mai 1996 forderte der Kläger vom Beklagten die Bezahlung von Schadenersatz in der Höhe von Fr. 127'680.-- zuzüglich Zins. Diese Forderung entspricht dem Betrag, den ihm die versäumte Haftungsklage gegen den Kanton Basel-Landschaft seiner Meinung nach eingebracht hätte.
Die Haftungsklage wäre ihrerseits auf Ersatz des durch die Haft entgangenen Verdienstes von monatlich US$ 6'000.-- (ca. Fr. 9'200.--) gerichtet gewesen, den der Beschwerdeführer ohne die erfolgte Inhaftierung gemäss behauptetem Arbeitsvertrag mit seiner Tätigkeit als Stewart und Reisebegleiter auf der Jacht "X._" des C._ in der Zeit von April 1988 bis zum Untergang der Jacht im September 1989 verdient hätte. Die Klage wurde unter Kosten- und Entschädigungsfolgen zulasten des Beschwerdeführers abgewiesen.
C.- Die anschliessende Berufung an das Obergericht des Kantons Zürich wies die II. Zivilkammer nach schriftlich durchgeführtem Berufungsverfahren mit Urteil vom 16. Mai 2000 ebenfalls ab. Gegen dieses Urteil führte der Kläger kantonale Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich. Das Kassationsgericht hiess die Nichtigkeitsbeschwerde bei grundsätzlicher Abweisung teilweise gut und strich die Erwägungen des obergerichtlichen Urteils zur Frage der Erfolgsaussichten der Staatshaftungsklage [ab Seite 7, "2. Abschnitt, 5. Zeile ("Auszugehen ist vom Gesetz. .."), bis Seite 9 unten ("...der Staatshaftungsklage des Klägers kein Erfolg beschieden gewesen wäre")].
D.- Mit der eidgenössischen Berufung vom 22. Juni 2000 beantragt der Kläger die Aufhebung des nach dem Urteil des Kassationshofes verbleibenden Entscheides und die Rückweisung der Streitsache an die Vorinstanz zur Neubeurteilung und zur Vervollständigung des Beweisergebnisses. Der Beklagte schliesst auf Abweisung der Berufung.

Das Bundesgericht zieht in Erwägung:
1.- Der Kläger rügt, dass die Vorinstanz die bundesrechtliche Beweisregel von Art. 8 ZGB und "von Art. 99 Abs. 3 i.V.m. Art. 42 Abs. 2 OR" verletzt hat.
Die Vorinstanz ist zutreffend davon ausgegangen, dass der den Ersatz eines angeblichen Schadens beanspruchende Kläger für den Schaden bzw. die entsprechenden anspruchsbegründenden Umstände beweispflichtig ist bzw. im Falle der Beweislosigkeit nach Art. 8 ZGB die Beweislast trägt. Dies gilt auch insoweit, als der Kläger behauptet, er hätte bei Durchführung des Staatshaftungsverfahrens seinen Schaden beweisen und entsprechenden Ersatz erhalten können. Der Kläger verkennt, dass der von ihm zu beweisende Schaden Voraussetzung sowohl seines (hypothetischen) Ersatzanspruchs im Staatshaftungsprozess wie seines Ersatzanspruchs im vorliegenden Prozess wegen sorgfaltspfswidriger Mandatsführung ist. Soweit der Kläger den Schaden im - wegen einer Sorgfaltswidrigkeit nicht geführten - Staatshaftungsprozess nicht hätte beweisen können, hat er auch keinen - von ihm im vorliegenden Verfahren ebenfalls zu beweisenden - Schaden erlitten. Insofern geht es nicht um hypothetische Schadensereignisse, sondern um tatsächlich (durch die sich als ungerechtfertigt erweisende Haft) erlittenen Schaden, den der Kläger als Anspruchsvoraussetzung zu beweisen hat. Art. 8 ZGB ist nicht verletzt.
Die Vorinstanz hat auch das (in der Tat auf überwiegende Wahrscheinlichkeit herabgesetzte, vgl. <ref-ruling> E. 3a S. 221) Beweismass für den Schaden und dessen Eintritt nicht verkannt. Sie hat die gesamten Aussagen des Zeugen als derart vage und unbestimmt qualifiziert, dass auf sie nicht abgestellt werden könne. Daraus ergibt sich, dass sie auch das hinreichende Mass an Wahrscheinlichkeit nicht als gegeben erachtet hat. Das (bundesrechtliche) Beweismass ist nicht verletzt.
2.-a) Gemäss Art. 51 Abs. 1 lit. c OG ist im kantonalen Entscheid das Ergebnis der Beweisführung festzuhalten und anzugeben, inwieweit das Urteil auf der Anwendung eidgenössischer, kantonaler oder ausländischer Gesetzesbestimmungen beruht. Die gerichtlichen Sachverhaltsfeststellungen haben ausreichend detailliert, vollständig und nicht widersprüchlich zu sein, um die Kontrolle der Rechtsanwendung zu gewährleisten (Poudret, COJ II, N 4 zu Art. 51 OG, S. 365).
Nach Art. 51 Abs. 1 lit. c OG haben die Parteien im Hinblick auf den Entscheid über das Einlegen einer Berufung Anspruch darauf, alle tatsächlichen und rechtlichen Erwägungen des kantonalen Richters zur Kenntnis nehmen zu können (Poudret, a.a.O., N 1 zu Art. 51 OG, S. 361).
Der Kläger wirft der Vorinstanz sinngemäss vor, in Verletzung des Art. 51 Abs. 1 lit. c OG entscheidende Beweissätze des von ihm behaupteten Arbeitsvertrages bezüglich des Zustandekommens, der Dauer und des Inhalts desselben im angefochtenen Urteil nicht festgehalten zu haben. Entgegen der Auffassung des Klägers hielt die Vorinstanz aber in ihrem Urteil bundesrechtskonform das aus ihrer Beweiswürdigung resultierende und für die Frage des Vertragsbestehens entscheidende Beweisergebnis vollständig und auch widerspruchsfrei fest. Indem das Obergericht in seinem Entscheid auf die vagen und widersprüchlichen Aussagen des Zeugen C._ verweist und deshalb nicht auf die vorgebrachten Beweismittel abstellen will, würdigt es lediglich die Beweise. Der Kläger verkennt den Inhalt des Art. 51 Abs. 1 lit. c OG, wenn er verlangt, dass Sachverhaltsbehauptungen festzuhalten sind, die nach der gerichtlichen Beweiswürdigung als unbewiesen gelten. Die Rüge des Klägers erschöpft sich in einer unzulässigen Kritik an der Beweiswürdigung und ist deshalb nicht zu hören.
b) Im Berufungsverfahren hat das Bundesgericht einer Entscheidung die tatsächlichen Feststellungen der letzten kantonalen Instanz als vollständig zu Grunde zu legen, es sei denn, sie seien im Hinblick auf den Tatbestand einer anwendbaren Sachnorm ergänzungsbedürftig (Art. 64 OG).
Werden solche Ausnahmen geltend gemacht, so hat die Partei, welche den Sachverhalt ergänzt wissen will, darüber genaue Angaben mit Aktenhinweisen zu machen. Eine Ergänzung setzt zudem voraus, dass entsprechende Sachbehauptungen bereits im kantonalen Verfahren prozesskonform aufgestellt, von der Vorinstanz aber zu Unrecht für unerheblich gehalten oder übersehen worden sind, was wiederum näher anzugeben ist; andernfalls gelten die Vorbringen als neu und damit unzulässig (Art. 55 Abs. 1 lit. c und d OG; <ref-ruling> E. 5c/aa S. 357 und 115 II 484 E. 2a S. 485 f., je mit Hinweisen).
Der Kläger wendet ein, die Vorinstanz verletze Art. 64 OG, indem sie nicht festgestellt habe, ob und inwieweit die Behauptungen des Klägers nach der Zeugenaussage C._ bezüglich Vertragsabschluss, Dauer und Höhe des Salärs als bewiesen gelten. Damit habe sie in ihrem Urteil Feststellungen zu Fragen nicht getroffen, die im Hinblick auf die Anwendung von Bundesrecht hätten abgeklärt werden müssen. Der Kläger unterlässt es jedoch, die Sachnorm zu nennen, hinsichtlich derer Anwendung er die tatsächlichen Feststellungen hätte ergänzt wissen wollen. Auf dieses Vorbringen des Klägers ist folglich nicht einzutreten.
3.- Da der Beweis für das Vorliegen eines Arbeitsvertrages gescheitert ist und demzufolge kein Schaden vorliegt, erübrigt sich die Prüfung weiterer Haftungsvoraussetzungen.
Mangels Rechtsschutzinteresses des Klägers hinsichtlich der nach seiner Auffassung vom Bundesgericht vorzunehmenden Überprüfung des hypothetischen Kausalzusammenhangs ist auf die entsprechende Rüge (Berufungsschrift Ziff. 9 und 10) ebenfalls nicht einzutreten.
4.- Nach diesen Erwägungen ist die Berufung, soweit auf sie einzutreten ist, abzuweisen und das Urteil des Obergerichts Zürich vom 16. Mai 2000 zu bestätigen. Bei diesem Verfahrensausgang wird der Kläger kosten- und entschädigungspflichtig (Art. 156 Abs. 1 und Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1.- Die Berufung wird abgewiesen, soweit darauf einzutreten ist und das angefochtene Urteil des Obergerichts des Kantons Zürich (II. Zivilkammer) bestätigt.
2.- Die Gerichtsgebühr von Fr. 5'000.-- wird dem Kläger auferlegt.
3.- Der Kläger hat den Beklagten für das bundesgerichtliche Verfahren mit Fr. 6'000.-- zu entschädigen.
4.- Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich (II. Zivilkammer) schriftlich mitgeteilt.
_
Lausanne, 23. November 2001
Im Namen der I. Zivilabteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: