A.- S._, geboren 1942, italienischer Staatsangehöriger, arbeitete als Grenzgänger in der Schweiz, zuletzt bei der Firma G._ als Maurer. Am 9. Oktober 1976 erlitt er bei einem Jagdunfall eine distale Humerusfraktur rechts. Nach dieser Verletzung stellten sich eine Ellbogenarthrose und eine eingeschränkte Ellbogenbeweglichkeit ein. Die Fortsetzung der angestammten Tätigkeit war nicht möglich. Am 13. Januar 1978 meldete er sich bei der Invalidenversicherung zum Rentenbezug. Auf Grund von Abklärungen der Invalidenversicherungs-Kommission des Kantons Graubünden (Mitteilung vom 4. Juli 1979) verfügte die Schweizerische Ausgleichskasse am 12. November 1979 die Ausrichtung einer halben Invalidenrente vom 1. Oktober 1977 bis 31. August 1978 und einer ganzen Rente ab dem 1. September 1978. Im Rahmen der auf Juli 1980 vorgesehenen Revision der Invalidenrente wurde der Invaliditätsgrad neu auf 60 % festgesetzt (Mitteilung der Invalidenversicherungs-Kommission des Kantons Graubünden 4. Juli 1980), worauf die Schweizerische Ausgleichskasse S._ mit Wirkung ab 1. August 1980 eine halbe Invalidenrente zusprach (Verfügung vom 16. Juli 1980). Der Rentenanspruch wurde in Revisionsverfahren der Jahre 1982, 1983, 1986, 1989, 1993 und 1996 bestätigt.
Mit Eingabe vom 4. Dezember 1996 machte S._ erneut eine Verschlechterung seines Gesundheitszustandes geltend. In der Folge nahm die IV-Stelle des Kantons Graubünden verschiedene medizinische Unterlagen zu den Akten, darunter Befundberichte italienischer Ärzte und ein Gutachten der Dres. med. E._ und H._, Spital X._, Medizinische Abteilung, vom 10. November 1997 mit Konsiliarberichten von Prof. Dr. med. C._, Spital X._, Orthopädische Abteilung, vom 25. September 1997 und von Dr. med. K._, Psychiatrische Klinik Y._, vom 1. Oktober 1997 sowie zwei ergänzenden Nachträgen von Dr. med. M._, Spital X._, vom 14. September 1998 und 4. Februar 1999. Nach Durchführung des Vorbescheidverfahrens (Schreiben vom 16. April 1999) und nachdem die Berufsberaterin einen neuen Einkommensvergleich erstellt hatte (Bericht vom 3. Juni 1999) lehnte die IV-Stelle des Kantons Graubünden das Rentenerhöhungsgesuch mit Verfügung vom 21. Juli 1999 ab. Eine dagegen beim Verwaltungsgericht des Kantons Graubünden erhobene Beschwerde wurde als gegenstandslos abgeschrieben, nachdem die IV-Stelle des Kantons Graubünden ihre Verfügung wegen Unzuständigkeit aufgehoben und die Akten an die IV-Stelle für Versicherte im Ausland überwiesen hatte. Diese erliess am 26. Oktober 1999 eine mit der aufgehobenen identische Verfügung, mit welcher das Revisionsgesuch abgewiesen wurde, da der Invaliditätsgrad 62,09 % betrage und sich damit am Rentenanspruch nichts ändere.
B.- S._ erhob dagegen bei der Eidgenössischen Rekurskommission der AHV/IV für die im Ausland wohnenden Personen (nachfolgend: Rekurskommission) Beschwerde und beantragte die Zusprechung einer ganzen Invalidenrente ab dem 31. Oktober 1983 und die Verzinsung der zurückbehaltenen Rente; ausserdem sei die Beschwerdegegnerin zur Kostentragung und zu einer Parteientschädigung zu verpflichten.
Die angerufene Instanz wies die Beschwerde mit Entscheid vom 20. März 2001 ab.
C.- Mit Verwaltungsgerichtsbeschwerde erneuert S._ die im vorinstanzlichen Prozess gestellten Rechtsbegehren. Die IV-Stelle für Versicherte im Ausland beantragt Abweisung der Beschwerde, während das Bundesamt für Sozialversicherung sich nicht vernehmen lässt.

Das Eidg. Versicherungsgericht zieht in Erwägung:
1.- Die Rekurskommission hat die massgeblichen Rechtsgrundlagen zutreffend dargelegt. Es betrifft dies die staatsvertraglichen (Art. 2 des Abkommens zwischen der Schweizerischen Eidgenossenschaft und der Italienischen Republik über Soziale Sicherheit vom 14. Dezember 1962) und gesetzlichen Bestimmungen sowie die Grundsätze über die Rentenrevision (Art. 41 IVG, Art. 87 Abs. 1 und 2 IVV; <ref-ruling> Erw. 1a mit Hinweisen), die dabei zu vergleichenden Sachverhalte (<ref-ruling> Erw. 2 mit Hinweis, 112 V 372 Erw. 2b,) den Umfang des Rentenanspruchs (Art. 28 Abs. 1 und 1ter IVG), die Ermittlung des Invaliditätsgrades nach der allgemeinen Methode des Einkommensvergleichs unter Beizug von Tabellenlöhnen zur Festlegung des hypothetischen Invalideneinkommens (Art. 28 Abs. 2 IVG; <ref-ruling> mit Hinweisen) und die Aufgabe des Arztes oder der Ärztin bei der Invaliditätsbemessung (ZAK 1991 S. 319 Erw. 1c mit Hinweisen; siehe auch <ref-ruling> Erw. 4 mit Hinweisen). Darauf wird verwiesen. Beizufügen ist, dass im Rahmen des Revisionsverfahrens für den Vergleich der massgebenden Sachverhalte einer Verfügung, welche die ursprüngliche Rentenverfügung (oder die letzte rentenändernde Revisionsverfügung) bloss bestätigt, keine Rechtserheblichkeit zukommt (<ref-ruling> Erw. 4; SVR 1999 IV Nr. 24 S. 72 Erw. 2a, je mit Hinweisen). Sodann haben sich die für die Invaliditätsschätzung massgebenden Vergleichseinkommen eines im Ausland wohnenden Versicherten nach der Rechtsprechung auf den gleichen Arbeitsmarkt zu beziehen, da die Unterschiede in den Lohnniveaus und den Lebensunterhaltskosten zwischen den Ländern es anders nicht gestatten, einen objektiven Vergleich der in Frage stehenden Einkommen vorzunehmen (<ref-ruling> Erw. 4b). Des Weitern ist nach der Rechtsprechung für den Beweiswert medizinischer Gutachten entscheidend, ob der Bericht für die streitigen Belange umfassend ist, auf allseitigen Untersuchungen beruht, auch die geklagten Beschwerden berücksichtigt, in Kenntnis der Vorakten (Anamnese) abgegeben worden ist, in der Darlegung der medizinischen Zusammenhänge und in der Beurteilung der medizinischen Situation einleuchtet und ob die Schlussfolgerungen des Experten oder der Expertin begründet sind. Bei einander widersprechenden medizinischen Berichten darf das Sozialversicherungsgericht den Prozess nicht erledigen, ohne das gesamte Beweismaterial zu würdigen und die Gründe anzugeben, warum es auf die eine und nicht auf die andere medizinische These abstellt (<ref-ruling> Erw. 3a mit Hinweisen).
2.- Streitig und zu prüfen ist, ob zwischen dem Erlass der Verfügung vom 16. Juli 1980 (Zusprechung einer halben Invalidenrente ab 1. August 1980) und der Revisionsverfügung vom 26. Oktober 1999 eine anspruchsbeeinflussende Änderung des Invaliditätsgrades eingetreten ist, sodass - bejahendenfalls - nunmehr Anspruch auf eine ganze Invalidenrente bestünde.
a) Im Bericht der Dres. med. E._ und H._, Spital X._, Medizinische Abteilung, vom 10. November 1997 wurden im Wesentlichen folgende Diagnosen gestellt: Schrotschussverletzung am rechten Arm mit Folgewirkungen (insbesondere eine Pseudoarthrose und eine starke Bewegungseinschränkung), koronare Herzkrankheit, Dysthymie bei aktueller depressiver Episode mit Somatisierung und rezidivierende Thoraxschmerzen bei degenerativen Veränderungen der Brustwirbelsäule. Die Beeinträchtigungen der psychischen Gesundheit und die Herzprobleme bleiben gemäss Bericht ohne Auswirkungen auf die Arbeitsfähigkeit. In seinem angestammten Beruf wurde der Versicherte als vollständig arbeitsunfähig, für leichtere Arbeiten, wie etwa als Pförtner oder Bürogehilfe, hingegen als "theoretisch noch teilweise arbeitsfähig" beurteilt. Auf Nachfrage seitens der IV-Stelle hin präzisierte Dr. med. M._ diese Stellungnahme in dem Sinne, dass eine konkrete Verweisungstätigkeit (Überwachungsfunktion in einer Getränke-Abfüllerei) aus medizinischer Sicht zu 50 % zumutbar sei, sofern der rechte Arm für die Ausübung dieser Tätigkeit nicht benutzt werden müsse (Bericht vom 4. Februar 1999).
Davon abweichend bezeichnete Prof. Dr. med. C._ in seinem Konsiliarbericht vom 25. September 1997 den Beschwerdeführer als "praktisch voll erwerbsunfähig". Eine vollständige Arbeitsunfähigkeit ("inabilità a qualsiasi lavoro proficuo e continuativo") auf Grund der Herzkrankheit bescheinigten die Dres. med. A._ und O._ in den Zeugnissen vom 10. Februar 1997 und 26. Juli 2000, was in auffälligem Kontrast zu den Angaben der Dres. med.
E._ und H._ steht. Angesichts dieser teils widersprüchlichen, teils nicht genügend bestimmten, teils ausschliesslich auf eine bestimmte Tätigkeit bezogenen Angaben zur gesundheitlichen Situation und deren Auswirkungen auf die Arbeitsfähigkeit ist der Sachverhalt medizinisch zu wenig abgeklärt, als dass ein Vergleich mit der Situation zum Zeitpunkt der letzten rentenändernden Verfügung möglich wäre. Die Verwaltung wird die nötigen Abklärungen zu treffen haben, insbesondere zum Mass der zumutbaren Arbeitsleistung in behinderungsangepassten Tätigkeiten.
b) In erwerblicher Hinsicht hat die Rekurskommission im Rahmen des Einkommensvergleichs, der Rechtsprechung (<ref-ruling> Erw. 3b/bb, 124 V 322 Erw. 3b/aa, je mit Hinweisen) folgend, das (nicht bestrittene) Valideneinkommen von Fr. 58'311.- in Beziehung gesetzt zu einem anhand der Tabellenlöhne (Schweizerische Lohnstrukturerhebung [LSE]), unter Vornahme des höchstmöglichen Abzuges von 25 % (<ref-ruling> Erw. 5b/cc), ermittelten Invalideneinkommen von Fr. 20'120.-, was einen Invaliditätsgrad von 65,5 % ergab.
Dieser Einkommensvergleich kann deswegen nicht bestätigt werden, weil die Annahme einer zumutbaren Arbeitsleistung von 50 % wie gezeigt (Erw. 2a), nicht auf gesicherten medizinischen Erkenntnissen beruht. Entgegen der Vorbringen in der Verwaltungsgerichtsbeschwerde ist hingegen korrekt, dass für die Festlegung des hypothetischen Invalideneinkommens auf den schweizerischen Arbeitsmarkt abgestellt wurde, ist doch auch das in den Einkommensvergleich einbezogene Valideneinkommen auf diesem Arbeitsmarkt erzielt worden (vgl. die in Erw. 1 angeführte Rechtsprechung).
Der Beschwerdeführer macht noch geltend, dass der errechnete Invaliditätsgrad von 65,5 % sehr nahe an den Wert heranreicht, ab welchem nach Art. 28 Abs. 1 IVG eine ganze Rente geschuldet ist. Das Eidgenössische Versicherungsgericht hat in einem kürzlich ergangenen Urteil festgehalten, dass nach der Festsetzung der einzelnen Faktoren zur Bestimmung des Invaliditätsgrades diese in die Berechnung einzusetzen sind, woraus ein notwendig bis auf die Kommastellen exaktes Ergebnis resultiert. Danach besteht kein Spielraum mehr für Aufrundungen, auch wenn der für die nächsthöhere Rentenstufe nötige Mindestinvaliditätsgrad nur knapp verfehlt wird (noch nicht in der Amtlichen Sammlung veröffentlichtes Urteil E. vom 8. August 2001, I 32/00).
3.- Der Antrag, die Gerichtskosten seien der Gegenpartei aufzuerlegen, ist gegenstandslos, da in der vorliegenden Streitsache für das letztinstanzliche Verfahren auf Grund von Art. 134 OG keine Verfahrenskosten erhoben werden.
Eine Parteientschädigung kann nicht zugesprochen werden.
Gemäss der Rechtsprechung (<ref-ruling>) hat eine nicht anwaltschaftlich vertretene Partei nur unter besonderen Voraussetzungen Anspruch auf eine Parteientschädigung, wobei namentlich vorausgesetzt wird, dass die Interessenwahrung einen hohen Arbeitsaufwand notwendig macht, welcher den Rahmen dessen überschreitet, was die einzelne Person üblicher- und zumutbarerweise auf sich zu nehmen hat. Diese Voraussetzung ist hier nicht erfüllt.

Demnach erkennt das Eidg. Versicherungsgericht:
I.Die Verwaltungsgerichtsbeschwerde wird in dem Sinne
gutgeheissen, dass der Entscheid der Eidgenössischen
Rekurskommission der AHV/IV für die im Ausland wohnenden
Personen vom 20. März 2001 und die Verfügung vom 26. Oktober 1999 aufgehoben werden und die Sache an
die IV-Stelle für Versicherte im Ausland zurückgewiesen
wird, damit sie, nach erfolgter Abklärung im Sinne
der Erwägungen, über den Rentenanspruch neu verfüge.
II.Es werden keine Gerichtskosten erhoben und keine Parteientschädigung zugesprochen.
III. Dieses Urteil wird den Parteien, der Eidgenössischen
Rekurskommission der AHV/IV für die im Ausland wohnenden
Personen, der Schweizerischen Ausgleichskasse, der
IV-Stelle des Kantons Graubünden und dem Bundesamt für
Sozialversicherung zugestellt.
Luzern, 30. Oktober 2001
Im Namen des
Eidgenössischen Versicherungsgerichts
Der Präsident der II. Kammer:
Der Gerichtsschreiber: