Abgangsentschädigung, hat sich ergeben:
A.- X._, geboren am ******, trat im Jahre 1969 in die Dienste der Radio Schweiz AG ein, wo er im Flug- und Seefunk tätig war. Auf den 1. Januar 1988 wechselte er zu den Fernmeldediensten der Generaldirektion PTT, da die Radio Schweiz AG weitgehend aufgelöst wurde. In der Folge ging der Flug- und Seefunkdienst von der Telecom PTT auf die Swisscom über, die im Herbst 1997 beschloss, diesen Bereich einzustellen bzw. auf eine private Trägerschaft zu übertragen.
Die Geschäftsstelle Network Services der Swisscom AG wurde beauftragt, Massnahmen im Zusammenhang mit dem dadurch bedingten Personalabbau auszuarbeiten. An einer im März 1998 durchgeführten Informationsveranstaltung wurde X._, dessen Stelle im Zuge der geplanten Umstrukturierungen aufgehoben werden sollte, auf entsprechende Frage hin vom Personalverantwortlichen - in Anwesenheit des Direktors der genannten Geschäftsstelle - bestätigt, dass auch beim Wechsel zu einer Bundesstelle eine Abgangsentschädigung ausgerichtet werde. Nachdem das Eidgenössische Departement für Umwelt, Verkehr, Energie und Kommunikation (UVEK) mit Schreiben vom 15. Mai 1998 X._ einen Anstellungsvertrag als Dienstchef im Generalsekretariat/Dienst für besondere Aufgaben unterbreitet hatte, kündigte er seine Anstellung bei der Swisscom auf den 31. Juli 1998. Im Kündigungsschreiben vom 25. Mai 1998 ersuchte er ausdrücklich darum, die "vorgesehene Abgangsentschädigung mit der letzten Lohnabrechnung auszubezahlen".
Die Swisscom AG bestätigte die Auflösung des Arbeitsverhältnisses am 26. Juni 1998 und teilte X._ gleichzeitig mit, die Abgangsentschädigung von Fr. 196'236.-- werde mit dem letzten Gehalt vom Juli 1998 überwiesen. Auf Grund einer Intervention der internen Revisionsstelle zahlte die Swisscom AG in der Folge die Abgangsentschädigung nicht aus. Sie informierte X._ mit Schreiben vom 3. August 1998 darüber, dass die Auszahlung einer Abgangsentschädigung gemäss Ziffer 10.1 der vorliegend anwendbaren Richtlinien 96/2000 der Telecom PTT auf die Aufgabe der Erwerbstätigkeit, den Übertritt in die Privatwirschaft und die Aufnahme einer selbstständigen Erwerbstätigkeit beschränkt sei; diese Aufzählung sei abschliessend; bei einem Wechsel zu einer Bundesstelle könne deshalb keine Abgangsentschädigung ausgerichtet werden. Die X._ erteilte, anderslautende Auskunft sei "rechtlich gesehen ... eine 'Falschauskunft einer amtlichen Behörde'", welche die Swisscom AG jedoch nicht zu binden vermöge, da er gestützt darauf noch keine nicht rückgängig zu machenden Dispositionen getroffen habe.
B.- Die Swisscom AG, Geschäftsstelle Network Services, verfügte am 1. Oktober 1998, X._ werde die in Aussicht gestellte Abgangsentschädigung in der Höhe von Fr. 196'236.-- wegen fehlender Rechtsgrundlage nicht ausbezahlt.
Auf die hiergegen erhobene Beschwerde trat die Swisscom AG, Headquarters, am 4. Juni 1999 nicht ein.
X._ focht den Entscheid mit Eingabe vom 12. Juli 1999 bei der Eidgenössischen Personalrekurskommission an. Diese hat die Beschwerde am 31. Mai 2000 teilweise gutgeheissen, den Beschwerdeentscheid der Swisscom AG, Headquarters, vom 4. Juni 1999 aufgehoben und die Swisscom AG verpflichtet, X._ eine Abgangsentschädigung von Fr. 125'000.-- auszubezahlen, zuzüglich 5 % Zins seit dem 1. August 1998.
Im Weiteren auferlegte sie ihm 3/8 der Verfahrenskosten von Fr. 3'200.-- (Spruch- und Schreibgebühren), nämlich Fr. 1'200.--, und sprach ihm eine reduzierte Parteientschädigung von Fr. 4'500.-- zu.
C.- X._ hat am 30. Juni 2000 Verwaltungsgerichtsbeschwerde beim Bundesgericht eingereicht mit dem Antrag, den Entscheid der Eidgenössischen Personalrekurskommission vom 31. Mai 2000 aufzuheben, insoweit ihm die Abgangsentschädigung im Umfang von Fr. 71'236.-- nicht zugesprochen, insoweit ihm Verfahrenskosten auferlegt und insoweit ihm nicht die volle Parteientschädigung ausgerichtet worden seien. Die Swisscom AG sei zu verpflichten, ihm den Betrag von Fr. 196'236.-- plus Zins zu 5 % seit 1. August 1998 zu bezahlen, plus vollen Parteikostenersatz für alle Instanzen.
Die Eidgenössische Personalrekurskommission hat mit Schreiben vom 19. Juli 2000 auf eine Vernehmlassung verzichtet.
Die Swisscom AG beantragt, die Verwaltungsgerichtsbeschwerde kostenfällig abzuweisen, soweit darauf einzutreten sei; angesichts der Komplexität der Streitsache sei der Swisscom AG ferner eine angemessene Parteientschädigung zuzusprechen.

Das Bundesgericht zieht in Erwägung:
1.- a) Die Verwaltungsgerichtsbeschwerde ist gemäss Art. 97 OG in Verbindung mit <ref-law> zulässig gegen Verfügungen, die sich auf öffentliches Recht des Bundes stützen oder hätten stützen sollen, sofern diese von einer der in Art. 98 OG genannten Vorinstanzen erlassen worden sind und keiner der in Art. 99 - 102 OG oder in der Spezialgesetzgebung vorgesehenen Ausschlussgründe vorliegt. Der angefochtene Entscheid geht von der Eidgenössischen Personalrekurskommission aus, die eine Vorinstanz des Bundesgerichts im Sinne von Art. 98 lit. e OG ist. Er stützt sich auf öffentliches Recht des Bundes, nämlich das Beamtengesetz vom 30. Juni 1927 (BtG; SR 172. 221.10), die Beamtenordnung 2 vom 15. März 1993 (BO 2; SR 172. 221.102. 1) und die Beamtenordnung Swisscom vom 4. November 1998 (BOS; SR 172. 221.102. 2). Ein Ausschlussgrund ist nicht gegeben (vgl. Art. 100 Abs. 1 lit. e OG). Auf die frist- und formgerecht eingereichte Eingabe des nach Art. 103 lit. a OG legitimierten Beschwerdeführers ist daher einzutreten.
b) Mit der Verwaltungsgerichtsbeschwerde kann der Beschwerdeführer die Verletzung von Bundesrecht, einschliesslich Überschreitung oder Missbrauch des Ermessens, rügen (Art. 104 lit. a OG). Da es sich bei der Personalrekurskommission um eine richterliche Behörde handelt, ist das Bundesgericht an deren Feststellung des Sachverhalts gebunden, soweit sie diesen nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen erhoben hat (Art. 104 lit. b in Verbindung mit Art. 105 Abs. 2 OG). Ausgeschlossen ist ferner die Rüge der Unangemessenheit, da keiner der im Gesetz vorgesehenen Ausnahmetatbestände vorliegt (Art. 104 lit. c OG).
c) Das Bundesgericht wendet im Verfahren der Verwaltungsgerichtsbeschwerde das Recht von Amtes wegen an, wobei es grundsätzlich an die Parteibegehren, nicht aber an die vorgebrachten Begründungen gebunden ist (Art. 114 Abs. 1 OG; <ref-ruling> E. 1 S. 513). Es kann die Beschwerde auch aus andern als den geltend gemachten Gründen gutheissen oder den angefochtenen Entscheid mit einer Begründung bestätigen, die von jener der Vorinstanz abweicht (<ref-ruling> E. 4a S. 117; <ref-ruling> E. 4a S. 203).
2.- Am 1. Januar 1998 ist das Bundesgesetz vom 30. April 1997 über die Organisation der Telekommunikationsunternehmung des Bundes (TUG; SR 784. 11) in Kraft getreten, mit welchem die Post-, Telefon- und Telegrafenbetriebe (PTT-Betriebe) in "Die schweizerische Post" (Post) und die Telekommunikationsunternehmung des Bundes (Swisscom AG) aufgeteilt worden sind. Gemäss <ref-law> gilt für das Personal der Swisscom AG bis zum Ablauf der Amtsdauer 1997 - 2000 die Gesetzgebung über das Bundespersonal. Art. 54 Abs. 1bis BtG bestimmt, dass bei einer durch Restrukturierung bedingten Auflösung von Dienstverhältnissen der Bundesrat die notwendigen Massnahmen zugunsten der betroffenen Beamten trifft; er kann namentlich angemessene Entschädigungen vorsehen. In der Botschaft vom 4. Oktober 1993 betreffend Änderung des Beamtengesetzes (BBl 1993 IV S. 512 ff.) wird dazu ausgeführt, Sinn der vorgeschlagenen Regelung sei vermehrte Flexibilität:
Der Bundesrat erhalte die Möglichkeit, bei grösseren Stellenabbau-Massnahmen Entschädigungen auszurichten; die Hürde zur Durchführung von notwendigen Reorganisationen werde damit gesenkt. Es werde jedoch kein genereller Anspruch auf eine Entschädigung verankert; der Bundesrat müsse von Fall zu Fall, abgestimmt auf die jeweiligen Umstände, über Notwendigkeit und Inhalt der zu treffenden Massnahmen entscheiden. Er werde von der Möglichkeit, Entschädigungen auszurichten, äusserst zurückhaltend Gebrauch machen. Massnahmen wie die Besetzung offener Stellen durch Personal, das von Entlassung bedroht sei, Versetzungen, Stellenvermittlung, Umschulung, Weiterbildung usw. kämen auf jeden Fall vor der Auflösung von Dienstverhältnissen mit Entschädigungen (BBl 1993 IV S. 523/524). Art. 54 Abs. 1bis BtG ist in der parlamentarischen Beratung ohne Änderung angenommen worden und am 1. Januar 1996 in Kraft getreten.
Der Bundesrat hat die ihm in Art. 54 Abs. 1bis BtG eingeräumte Kompetenz an die Betriebe delegiert, die gemäss Art. 85 BO 2 für ihren Bereich die Rahmenbedingungen erlassen und die Entschädigungen festsetzen. Die PTT-Betriebe haben dazu in den Personalvorschriften betreffend das Dienstverhältnis der PTT-Beamtinnen und -Beamten festgehalten, das Generaldirektorium erlasse zu Art. 85 BO 2 eine besondere Rahmenordnung. Entschädigungen würden nur ausgerichtet, sofern den Betroffenen keine zumutbare Stelle angeboten werden könne oder bei der Anstellung bzw. bei der Wiederwahl kein entsprechender Vorbehalt angebracht worden sei (Dienstordner C1, Ausgabe 1996, Ziff. 8501 S. 109). Die genannte Rahmenordnung erging am 2. April 1996 als dienstliche Weisung des Generaldirektors des Departements Telecom mit den Richtlinien 96/2000 für flexible Personalmassnahmen bei betrieblichen Veränderungen (RL 96/2000). Diese Richtlinien sind weiterhin - also auch im vorliegenden Fall - massgebend: Obwohl für das Personal der Swisscom AG seit dem 1. Dezember 1998 die Beamtenordnung Swisscom (BOS) gilt, gemäss deren Art. 85 die Swisscom AG bei Auflösung des Dienstverhältnisses infolge Aufhebung des Amtes selber die Rahmenbedingungen erlassen und Entschädigungen festsetzen kann, sind solche Regelungen bis anhin offenbar nicht ergangen.
Nach Ziff. 10 der Richtlinien 96/2000, welche die Abgangsentschädigung bei freiwilligem Austritt ohne Rentenfolge regelt, hat grundsätzlich jeder von Restrukturierungsmassnahmen betroffene Bedienstete Anspruch auf eine Weiterbildung in einem zumutbaren Aufgabenbereich. Eine Abgangsentschädigung darf nur dann ausgerichtet werden, wenn der Betroffene freiwillig und auf ausdrücklichen eigenen Wunsch beabsichtigt, das Arbeitsverhältnis mit Telecom PTT (bzw.
nun Swisscom AG) aufzulösen (Aufgabe der Erwerbstätigkeit, Übertritt in die Privatwirtschaft oder Aufnahme einer selbstständigen Erwerbstätigkeit) und zum Zeitpunkt dieses Entscheides noch kein zumutbares Aufgabengebiet angeboten werden kann.
3.- a) Die Eidgenössische Personalrekurskommission (im Folgenden: Rekurskommission) hat erwogen, es widerspreche dem Sinn der Richtlinien 96/2000, die in Ziff. 10 geregelte Abgangsentschädigung bei einem Wechsel zu einer Stelle in der Bundesverwaltung, zu welcher auch die Telecom PTT gehörte, auszurichten. Für die Ausrichtung einer Abgangsentschädigung genüge nicht, dass das Dienstverhältnis freiwillig aufgelöst worden sei; vielmehr müssten die in Klammer beigefügten zusätzlichen Voraussetzungen, nämlich entweder die Aufgabe der Erwerbstätigkeit, der Übertritt in die Privatwirtschaft oder die Aufnahme einer selbstständigen Erwerbstätigkeit ebenfalls alternativ erfüllt sein. So lege auch Ziff. 8.1 ausdrücklich fest, dass die bei einem freiwilligen Übertritt zu einer Partner- oder Tochterunternehmung der Telecom PTT grundsätzlich vorgesehenen finanziellen Anreize entfielen, sofern eine zumutbare Weiterbeschäftigung innerhalb der Telecom PTT oder einer anderen Stelle des Bundes angeboten werden könne.
Damit sei dem Beschwerdeführer die Abgangsentschädigung für den Fall eines Wechsels zu einer Bundesstelle von der Swisscom AG zu Unrecht zugesichert worden. Indessen habe er gemäss dem in <ref-law> verankerten, vordem aus Art. 4 aBV abgeleiteten Grundsatz von Treu und Glauben Anspruch auf Schutz seines berechtigten Vertrauens in die ihm gegenüber von der Swisscom AG abgegebene Zusicherung; die diesbezüglich in der Rechtsprechung entwickelten Voraussetzungen seien vorliegend erfüllt. Die dem Beschwerdeführer anlässlich einer Informationsveranstaltung vom Personalverantwortlichen erteilte Auskunft, dass auch bei einem Wechsel zu einer Stelle in der Bundesverwaltung Anspruch auf eine Abgangsentschädigung bestehe, habe sich auf eine konkrete den Beschwerdeführer betreffende Angelegenheit bezogen und sei von der zuständigen (Amts)Stelle ausgegangen; ebenso stehe keine Rechtsänderung zwischen Auskunftserteilung und Kündigung zur Diskussion. Sodann ergebe sich aus den Akten, dass der Personalverantwortliche auch dann noch die Auffassung vertreten habe, die Auszahlung sei richtlinienkonform, als diese durch das interne Revisorat bereits gestoppt worden war; die Swisscom AG hätte nämlich dem ohne Vorbehalt zum Beamten gewählten Beschwerdeführer, der nach der Aufgabe des Flug- und Seefunks freigestellt worden wäre, den Lohn bis zum Ende der Amtsdauer bezahlen müssen, sodass es für sie bezüglich der Auszahlung der Abgangsentschädigung keinen Unterschied gemacht habe, ob der Beschwerdeführer in die Privatwirtschaft wechseln oder eine Bundesstelle annehmen würde. Auch wenn eine solche rein wirtschaftliche Betrachtungsweise dem Sinn der Richtlinien, die die soziale Verträglichkeit der erforderlichen Personalmassnahmen sicherstellen wollten, nicht entsprochen habe, liesse sich unter den gegebenen Umständen doch nicht sagen, dass der Beschwerdeführer nicht hätte gutgläubig sein dürfen und über die ihm erteilte Auskunft hinaus weitere Nachforschungen hätte anstellen müssen. Zudem lege der Beschwerdeführer glaubhaft dar, dass, wenn bei einem Wechsel zu einer Bundesstelle keine Abgangsentschädigung geleistet worden wäre, er die Anstellung bei der Y._ GmbH vorgezogen hätte. Indem er das Dienstverhältnis bei der Swisscom AG gekündigt und eine Bundesstelle angenommen habe, habe er deshalb eine für ihn nicht wieder gutzumachende Disposition getroffen.
Bei dieser Sachlage habe der Beschwerdeführer nach Treu und Glauben Anspruch darauf, dass ihm der infolge der unrichtigen Auskunft entstandene Schaden ersetzt werde, er mithin nicht schlechter gestellt werde, als wenn ihm eine richtige Auskunft erteilt worden wäre. Unter Berücksichtigung der Lohndifferenz und der schlechteren beruflichen Vorsorge bei der genannten Stelle in der Privatwirtschaft sei die Abgangsentschädigung nach richterlichem Ermessen auf Fr. 125'000.-- festzusetzen. Im Weiteren handle es sich - entgegen der Ansicht des Beschwerdeführers - beim Schreiben der Swisscom AG vom 26. Juni 1998, in welchem die Auflösung des Dienstverhältnisses bestätigt und festgehalten werde, dass die Swisscom AG die Abgangsentschädigung von Fr. 196'236.-- mit dem letzten Gehalt vom Juli 1998 überweisen werde, nicht um eine Verfügung, da einerseits die diesbezüglichen Anforderungen gemäss <ref-law> nicht erfüllt seien und andererseits nicht ein Rechtsverhältnis verbindlich geregelt werde, sondern bloss eine schon früher erfolgte Zusicherung bestätigt worden sei. Im Übrigen wäre auch beim Widerruf einer Verfügung - gleich wie beim Schutz des Vertrauens in eine behördliche Auskunft - zu berücksichtigen gewesen, welche Situation sich ohne fehlerhafte Verfügung ergeben hätte, sodass sich am Ergebnis nichts ändern würde.
b) Der Beschwerdeführer macht geltend, die Folgerung der Rekurskommission, das Schreiben der Swisscom AG vom 26. Juni 1998 habe nur die schon früher zugesicherte Abgangsentschädigung bestätigt, sei rechtswidrig. Richtigerweise handle es sich bei dem genannten Schreiben um eine Verfügung, gemäss welcher er Anspruch auf die darin festgesetzte Abgangsentschädigung von Fr. 196'236.-- habe. Die Voraussetzungen für einen Widerruf seien vorliegend nicht erfüllt.
Zum einen sei die zusichernde Verfügung nicht rechtsfehlerhaft; namentlich genüge auf Grund des Wortlautes von Ziff. 10 der Richtlinien 96/2000 die freiwillige Auflösung des Arbeitsverhältnisses für die Ausrichtung einer Abgangsentschädigung.
Dass die Swisscom AG nun in Änderung ihrer früheren Praxis davon ausgehe, es müssten weitere Voraussetzungen erfüllt sein, stelle keinen Widerrufsgrund dar. Die Verfügung vom 26. Juni 1998 sei in materielle und formelle Rechtskraft erwachsen und könne zudem als begünstigende Verfügung ohnehin nicht widerrufen werden, gerade auch, weil er, indem er die Stelle bei der Bundesverwaltung angenommen und jene bei der Y._ GmbH abgelehnt habe, nicht rückgängig zu machende Dispositionen getroffen habe. Im Weiteren beruhe die von der Vorinstanz wegen falscher Auskunft zugesprochene Entschädigung hinsichtlich seiner Salärmöglichkeiten auf reiner Hypothese. Diese Schlussfolgerungen seien als Rechtsfrage vom Bundesgericht frei zu prüfen bzw. , sofern sie als Sachverhaltsfeststellungen qualifiziert würden, offensichtlich unrichtig. Das Verhalten der Swisscom AG, welche die zugesicherte Abgangangsentschädigung nun verweigere, obwohl er selber seine Leistung (die Kündigung) erbracht habe, sei ein krasser Verstoss gegen Treu und Glauben und verdiene keinen Rechtsschutz.
4.- a) Soweit die Swisscom AG gestützt auf <ref-law> öffentlichrechtliche Funktionen der früheren PTT-Betriebe übernommen hat, gilt das Bundesgesetz über das Verwaltungsverfahren (vgl. <ref-law>). Gemäss <ref-law> sind schriftliche Verfügungen, auch wenn die Behörde sie in Briefform eröffnet, als solche zu bezeichnen, zu begründen und mit einer Rechtsmittelbelehrung zu versehen.
Das Schreiben der Swisscom AG vom 26. Juni 1998, das die Auflösung des Dienstverhältnisses bestätigt und die Auszahlung der Abgangsentschädigung regelt, entspricht diesen Erfordernissen zwar nicht. Da die Swisscom AG mit dem genannten Schreiben dem Begehren des Beschwerdeführers entsprach, war das indessen auch nicht nötig (<ref-law>). Die Vorinstanz übersieht, dass der Beschwerdeführer das Dienstverhältnis nicht durch Kündigung im eigentlichen Sinn, d.h. durch einseitige Willenserklärung, auflösen konnte; vielmehr hatte die Behörde die Entlassung zu bewilligen (Art. 53 Abs. 1 BtG, vgl. auch Art. 84 BOS). Das konnte nur durch - mitwirkungs- bzw. zustimmungsbedürftige - Verfügung geschehen, mit welcher das konkrete Rechtsverhältnis zwischen der Swisscom AG und dem Beschwerdeführer verbindlich aufgehoben wurde. Das "Kündigungsschreiben" vom 25. Mai 1998 stellte insofern nur ein Gesuch um Entlassung dar. Da diesem entsprochen wurde, war eine besondere Form entbehrlich. Das Schreiben der Swisscom AG vom 26. Juni 1998 unterscheidet sich in formeller Hinsicht denn auch kaum vom Ernennungsschreiben der PTT-Betriebe vom 15. Dezember 1987, dem zweifellos Verfügungscharakter zukommt. Dass im Schreiben vom 26. Juni 1998 nur die Auflösung des Dienstverhältnisses, jedoch nicht die Festsetzung der Abgangsentschädigung, verfügungsmässig verbindlich geregelt werden sollte, ist schon deshalb nicht anzunehmen, weil der Swisscom AG auf Grund der mehrmaligen Anfragen des Beschwerdeführers klar sein musste, dass dessen Entlassungsgesuch an die Bedingung der Zusprechung einer Abgangsentschädigung im zugesicherten Umfang geknüpft war. Daran ändert nichts, dass im Schreiben vom 26. Juni 1998 auch Nebensächlichkeiten der Entlassung (wie Schlüsselrückgabe und dergleichen) geregelt wurden.
b) Ist deshalb davon auszugehen, dass die Abgangsentschädigung in der Höhe von Fr. 196'236.-- durch Verfügung zugesprochen worden ist, muss im Folgenden geprüft werden, ob die Voraussetzungen für einen Widerruf erfüllt sind.
5.- a) Nach der bundesgerichtlichen Rechtsprechung kann eine materiell unrichtige Verfügung nach Ablauf der Rechtsmittelfrist unter bestimmten Voraussetzungen zurückgenommen werden. Dabei sind das Interesse an der richtigen Durchführung des objektiven Rechts und dasjenige an der Wahrung der Rechtssicherheit gegeneinander abzuwägen. In der Regel geht das Postulat der Rechtssicherheit dem Interesse an der Durchsetzung des objektiven Rechts vor und ist ein Widerruf nicht zulässig, wenn durch die Verwaltungsverfügung ein subjektives Recht begründet worden oder die Verfügung in einem Verfahren ergangen ist, in dem die sich gegenüberstehenden Interessen allseitig zu prüfen und gegeneinander abzuwägen waren, oder wenn der Private von einer ihm durch die Verfügung eingeräumten Befugnis bereits Gebrauch gemacht hat.
Diese Regel gilt allerdings nicht absolut; auch in diesen drei Fällen kann ein Widerruf in Frage kommen, wenn er durch ein besonders gewichtiges öffentliches Interesse geboten ist (<ref-ruling> E. 4c S. 310, mit Hinweisen; <ref-ruling> E. 1a/aa S. 276; zur früheren Rechtsprechung, vgl. <ref-ruling> E. 4 S. 343/344).
b) Streitig ist zunächst, ob überhaupt eine rechtsfehlerhafte Verfügung vorliegt. Der Beschwerdeführer stellt sich auf den Standpunkt, die anwendbaren Richtlinien 96/2000 der Telecom PTT stellten rechtlich innerdienstliche - nicht zwingende - Weisungen an die Personalverantwortlichen dar, die abweichenden Lösungen im Einzelfall nicht entgegenstünden.
Bei den Richtlinien 96/2000 handelt es sich nicht um verbindliche Rechtssätze (Erlasse), sondern um allgemeine Dienstanweisungen generell-abstrakter Natur, welche die Schaffung einer einheitlichen Verwaltungspraxis bezwecken (vgl. <ref-ruling> E. 2b S. 478, mit Hinweisen). Da sie nicht vom verfassungsmässigen Gesetzgeber, sondern von einer Verwaltungsbehörde - hier der Telecom PTT - stammen, können sie keine von der gesetzlichen Ordnung abweichenden Bestimmungen vorsehen (<ref-ruling> E. 2a S. 345; <ref-ruling> E. 2b S. 478). Wie ausgeführt (E. 2), wurde 1994/1995 im Rahmen der Teilrevision des Beamtengesetzes mit Art. 54 Abs. 1bis BtG die gesetzliche Grundlage für sozialverträgliche Lösungen zugunsten des von Restrukturierungsmassnahmen innerhalb der Verwaltung betroffenen Personals geschaffen (vgl. Votum des Berichterstatters im Ständerat, Frick:
"... auch ein Instrumentarium für einen allfälligen Sozialplan ..."; AB S 1995 70). Die in Art. 54 Abs. 1bis BtG vorgesehenen Entschädigungen stehen deshalb jenen im Rahmen eines Sozialplanes ausgerichteten nahe; ihr Zweck ist damit, die durch die Auflösung des Dienstverhältnisses allenfalls beeinträchtigte Altersvorsorge sicherzustellen (z.B. bei vorzeitigen Pensionierungen) sowie wirtschaftliche Härten (z.B. beim Aufbau einer selbstständigen Existenz) zu mildern (vgl. Matthias W. Rickenbach, Die Nachwirkungen des Arbeitsverhältnisses, Bern 2000, S. 101 ff., S. 107/108; Roland A.
Müller, Abfindungen in Sozialplänen und ihre sozialversicherungsrechtliche Behandlung, AJP 3/99, S. 286 ff., S. 287).
Dieser Zweckbestimmung entspricht Ziff. 10.1 der Richtlinien 96/2000, wonach eine Abgangsentschädigung nur bei Aufgabe der Erwerbstätigkeit, Übertritt in die Privatwirtschaft oder Aufnahme einer selbstständigen Erwerbstätigkeit ausgerichtet werden darf. Die dem Beschwerdeführer von der Swisscom AG auch für den Fall des Wechsels zu einer Bundesstelle zugesicherte Abgangsentschädigung steht deshalb in Widerspruch zu den massgeblichen gesetzlichen Regelungen; die entsprechende Verfügung vom 26. Juni 1998 ist materiell unrichtig.
c) Zu prüfen bleibt, ob das Interesse an der richtigen Durchführung des objektiven Rechts dasjenige an der Wahrung der Rechtssicherheit überwiegt.
Die Verfügung vom 26. Juni 1998, mit welcher dem Beschwerdeführer die Auszahlung der Abgangsentschädigung bestätigt wurde, erging nicht in einem besonders qualifizierten Verfahren, in dem die sich gegenüberstehenden Interessen umfassend geprüft und gegeneinander abgewogen worden wären (vgl. E. 5a). Ebenso wenig wurde dem Beschwerdeführer damit eine Befugnis eingeräumt, von der er bereits Gebrauch gemacht hätte. Dieses auf Bewilligungen zugeschnittene Erfordernis könnte im vorliegenden Fall ohnehin nur sinngemäss Anwendung finden; indessen hat der Beschwerdeführer zwischen dem 26. Juni 1998 und dem 28. Juli/3. August 1998, als die Auszahlung des Betrages gestoppt wurde, bzw. dem 1. Oktober 1998, als die Verfügung widerrufen wurde, weder über die Abfindung verfügt noch gestützt auf die Verfügung anderweitige nicht wieder rückgängig zu machende Dispositionen getroffen.
Ob allenfalls der in diesem Zusammenhang von ihm geltend gemachte Privatschulbesuch seines Sohnes hierzu zu zählen wäre, kann dahingestellt bleiben, da die entsprechenden Schulgebühren dem Beschwerdeführer ohnehin insofern zu ersetzen wären, als er Anspruch auf Ersatz des Vertrauensschadens hätte (vgl. E. 6). Ebenfalls davon zu unterscheiden sind die Dispositionen, die der Beschwerdeführer auf Grund der Zusicherungen vom Frühling 1998 getroffen hatte - nämlich die Kündigung -, die nichts damit zu tun haben, ob und inwiefern er über den zugesicherten Betrag bereits verfügte.
Sodann wurde dem Beschwerdeführer durch die blosse verfügungsweise Zusprechung der Abgangsentschädigung auch nicht ein eigentliches subjektives Recht eingeräumt (vgl. hierzu Fritz Gygi, Verwaltungsrecht, Bern 1986, S. 312, 164/165), da für die diesbezüglich erforderliche erhöhte Rechtsbeständigkeit der Umstand allein, dass verfügt wurde, nicht genügen kann (vgl. Ulrich Häfelin/Georg Müller, Grundriss des Allgemeinen Verwaltungsrechts, Zürich 1998, 3. Aufl. , N 815, S. 203, wo in diesem Zusammenhang denn auch von wohlerworbenen Rechten gesprochen wird; ebenso Gygi, a.a.O., S. 165, wonach das subjektive öffentliche Recht dem wohlerworbenen Recht gleicht; a.M. betreffend begünstigende Verfügungen offenbar: Blaise Knapp, Grundlagen des Verwaltungsrechts, Basel 1992, N 1283 S. 279, N 1287 ff. S. 280). Eine solche besondere Rechtsbeständigkeit haftet der Verfügung vom 26. Juni 1998 jedenfalls nicht an, da finanziellen Ansprüchen von Beamten in der Regel nicht der Charakter wohlerworbener Rechte zukommt (<ref-ruling> E. 5b S. 255/256, mit Hinweis; Urteil vom 2. Juli 1999 in Praxis 2/2000 Nr. 22, E. 3b).
Die Swisscom AG hat - namentlich auch aus Gründen der rechtsgleichen Behandlung des austretenden Personals, zu der sie, soweit sie öffentlichrechtliche Funktionen wahrnahm, verpflichtet war - ein beachtliches Interesse daran, nur die in den massgeblichen Richtlinien 96/2000 vorgesehenen Abgangsentschädigungen zu bezahlen. Wenn der Beschwerdeführer dagegen vorbringt, es sei vor dem Grundsatz der Rechtsgleichheit nicht haltbar, dass an Mitarbeiter, die in die Privatwirtschaft wechselten oder selbstständig würden, eine Abgangsentschädigung geleistet werde, verkennt er, dass diesfalls gerade wegen der damit hinsichtlich der Altersvorsorge verbundenen Risiken die Richtlinien 96/2000 ausdrücklich einen solchen Anspruch einräumen (vgl. E. 5b). Demgegenüber erlitt er mit dem Wechsel zu einer Bundesstelle keine finanziellen Einbussen, wurde er doch offenbar in der gleichen Lohnklasse eingestellt (vgl. Verfügung Swisscom AG vom 1. Oktober 1998, S. 4, und Anstellungsvertrag UVEK vom 15. Mai 1998) und blieb auch seine Altersvorsorge im bisherigen Rahmen gewährleistet. Damit überwiegt vorliegend das Interesse an der richtigen Anwendung des objektiven Rechts gegenüber der Wahrung der Rechtssicherheit. Die rechtsfehlerhafte Verfügung darf deshalb zurückgenommen werden. Daran ändert nichts, dass die Swisscom AG im Zeitpunkt der Zusicherung der Abgangsentschädigung wusste, dass der Beschwerdeführer in die Bundesverwaltung wechseln würde. Ebenso wenig kann - entgegen den Ausführungen des Beschwerdeführers - den für das Bundesgericht verbindlichen Sachverhaltsfeststellungen der Vorinstanz (Art. 105 Abs. 2 OG) entnommen werden, dass die Swisscom AG mit dem fraglichen Widerruf eine Praxisänderung vorgenommen hätte.
6.- Indessen hat der Beschwerdeführer gemäss den Grundsätzen des Vertrauensschutzes Anspruch auf Ersatz des ihm aus der unrichtigen Auskunft der Swisscom AG erwachsenen Schadens. Der Beschwerdeführer konnte die Unrichtigkeit dieser Auskunft nicht ohne weiteres erkennen und hat gestützt darauf eine nicht wieder rückgängig zu machende Disposition, nämlich die Kündigung, getroffen. Der ihm dadurch entstandene Schaden ist deshalb zu ersetzen. Dass mit einer solchen Entschädigung von vornherein nur die dem Beschwerdeführer tatsächlich erwachsenen Nachteile ausgeglichen werden dürfen und er nicht darüber hinaus begünstigt werden soll, liegt auf der Hand (vgl. auch Beatrice Weber-Dürler, Vertrauensschutz im öffentlichen Recht, Basel 1983, § 14 II C, S. 141/142). Ein voller Ersatz bzw. die Zusprechung der gesamten ursprünglich festgesetzen Abgangsentschädigung kann daher nicht in Betracht kommen. Die Personalrekurskommission hat diesbezüglich ausgeführt, gemäss eigenen Aussagen hätte der Beschwerdeführer, wäre ihm mitgeteilt worden, dass bei einem Wechsel zu einer Bundesstelle keine Abgangsentschädigung ausbezahlt werde, eine Anstellung bei der Y._ GmbH angenommen. In diesem Fall hätte er nach den für das Bundesgericht verbindlichen Sachverhaltsfeststellungen der Vorinstanz eine Lohneinbusse von 5 bis 10 Prozent und eine Verschlechterung der beruflichen Vorsorge hinnehmen müssen. Die gegenteiligen Behauptungen des Beschwerdeführers beruhen auf blossen Spekulationen; daraus ergibt sich jedenfalls nicht, dass die Vorinstanz den Sachverhalt offensichtlich unrichtig erhoben hätte (vgl. <ref-ruling>, nicht veröffentlichte E. 4; <ref-ruling> E. 4a S. 199/200; vgl. auch Peter Karlen, Verwaltungsgerichtsbeschwerde, in: Handbücher für die Anwaltspraxis, Prozessieren vor Bundesgericht, Basel 1998, 2. Aufl. , Rz. 3.61 S. 110/111).
Wenn die Personalrekurskommission in Würdigung der gesamten Umstände von einem dem Beschwerdeführer entstandenen Vertrauensschaden von Fr. 125'000.-- ausgegangen ist, wurde er damit grosszügig entschädigt. Dem Bundesgericht ist es im Übrigen verwehrt, den nach richterlichem Ermessen festgesetzten Betrag auf seine Angemessenheit zu überprüfen (Art. 104 lit. c e contrario).
7.- Die Verwaltungsgerichtsbeschwerde erweist sich demnach als unbegründet und ist abzuweisen.
Dem Ausgang des Verfahrens entsprechend sind die Kosten dem Beschwerdeführer aufzuerlegen (Art. 156 Abs. 1 in Verbindung mit Art. 153 und 153a OG; <ref-ruling> E. 6 S. 208). Die Swisscom AG hat eine Parteientschädigung beantragt.
Gemäss Art. 159 Abs. 2 OG darf im Verfahren der Verwaltungsgerichtsbeschwerde obsiegenden Behörden oder mit öffentlichrechtlichen Aufgaben betrauten Organisationen in der Regel keine Parteientschädigung zugesprochen werden. Die Swisscom AG war - wie ausgeführt - auf Grund von <ref-law> verpflichtet, das bestehende Dienstverhältnis des Beschwerdeführers bis zum Ablauf der Amtsdauer 1997 - 2000 als Arbeitgeberin weiterzuführen. Da sie insofern öffentlichrechtliche Funktionen zu übernehmen hatte, hat sie im vorliegenden Verfahren keinen Anspruch auf Parteientschädigung. Dass sie anwaltlich vertreten war, ändert daran nichts.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Die Gerichtsgebühr von Fr. 3'000.-- wird dem Beschwerdeführer auferlegt.
3.- Dieses Urteil wird den Parteien und der Eidgenössischen Personalrekurskommission schriftlich mitgeteilt.
_
Lausanne, 15. Februar 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Die Gerichtsschreiberin: