Aufenthaltsbewilligung, hat sich ergeben:
A.- N.E._, geb. 1956, schweizerischer Staatsangehöriger, heiratete am 24. Dezember 1997 in Mazedonien die mazedonische Staatsangehörige E.E._, geb. 1966. Am 5. April 1998 reiste die Ehefrau im Rahmen des Familiennachzugs in die Schweiz ein. Sie erhielt eine Aufenthaltsbewilligung, gültig bis 4. April 1999. E.E._ hat drei Kinder aus erster Ehe, welche in Mazedonien zurückblieben.
B.- Am 29. März 1999 lehnte die Fremdenpolizei des Kantons St. Gallen die Verlängerung der Aufenthaltsbewilligung ab, weil sie zum Schluss gekommen war, dass es sich um eine blosse Scheinehe handle. Einen von N.E._ eingereichten Rekurs wies das Justiz- und Polizeidepartement mit Entscheid vom 20. Dezember 1999 ab.
Mit Urteil vom 16. März 2000 wies auch das Verwaltungsgericht des Kantons St. Gallen die von N.E._ erhobene Beschwerde ab.
C.- Am 5. Mai 2000 hat N.E._ Verwaltungsgerichtsbeschwerde an das Bundesgericht erhoben. Er beantragt, das Urteil des Verwaltungsgerichts vom 16. März 2000 aufzuheben und die Aufenthaltsbewilligung seiner Ehefrau zu verlängern.
Im Übrigen ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung für das bundesgerichtliche Verfahren wie auch für dasjenige vor Verwaltungsgericht.
Das Justiz- und Polizeidepartement und das Verwaltungsgericht des Kantons St. Gallen sowie das Bundesamt für Ausländerfragen beantragen die Abweisung der Verwaltungsgerichtsbeschwerde.

Das Bundesgericht zieht in Erwägung:
1.- a) Nach Art. 100 Abs. 1 lit. b Ziff. 3 OG ist die Verwaltungsgerichtsbeschwerde auf dem Gebiete der Fremdenpolizei unzulässig gegen die Erteilung oder Verweigerung von Bewilligungen, auf die das Bundesrecht keinen Anspruch einräumt.
Gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) entscheidet die zuständige Behörde, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt oder Niederlassung. Es besteht damit grundsätzlich kein Anspruch auf Erteilung einer Aufenthaltsbewilligung, es sei denn, der Ausländer könne sich auf eine Sondernorm des Bundesrechts oder eines Staatsvertrags berufen (<ref-ruling> E. 2a S. 291, 361 E. 1a S. 364; <ref-ruling> E. 1b S. 147, je mit Hinweisen).
b) Gemäss Art. 7 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung (Abs. 1 Satz 1); der Anspruch erlischt, wenn ein Ausweisungsgrund vorliegt (Abs. 1 Satz 3). Kein Anspruch besteht, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern und namentlich jene über die Begrenzung der Zahl der Ausländer zu umgehen (Abs. 2). Für die Zulässigkeit der Verwaltungsgerichtsbeschwerde kommt es nur darauf an, ob formell eine eheliche Beziehung besteht. Die Frage, ob im konkreten Fall die Voraussetzungen zur Verfolgung des Anspruches erfüllt sind, namentlich ob wegen einer Scheinehe eine Ausnahme vorliegt, ist materieller Natur (<ref-ruling> E. 2b S. 18). Auf die Verwaltungsgerichtsbeschwerde ist daher einzutreten.
2.- a) Der ausländische Ehegatte eines Schweizer Bürgers hat nach Art. 7 Abs. 2 ANAG dann keinen Anspruch auf die ihm nach Abs. 1 dieser Bestimmung grundsätzlich zustehende Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern zu umgehen.
Dass Ehegatten mit der Heirat nicht eine eheliche Lebensgemeinschaft begründen, sondern die Vorschriften über Aufenthalt und Niederlassung von Ausländern umgehen wollen, entzieht sich in der Regel dem direkten Beweis und kann diesfalls, wie das bereits früher bei der Bürgerrechtsehe zutraf (vgl. dazu <ref-ruling>), nur durch Indizien nachgewiesen werden. Ein solches Indiz lässt sich darin erblicken, dass dem Ausländer die Wegweisung drohte, etwa weil er ohne Heirat keine Aufenthaltsbewilligung erhalten hätte oder sie ihm nicht verlängert worden wäre. Für das Vorliegen einer Ausländerrechtsehe können sodann die Umstände und die kurze Dauer der Bekanntschaft sprechen sowie insbesondere die Tatsache, dass die Ehegatten eine Wohngemeinschaft gar nie aufgenommen haben. Dasselbe gilt, wenn für die Heirat eine Bezahlung vereinbart wurde. Dass die Begründung einer wirklichen Lebensgemeinschaft gewollt war, kann umgekehrt nicht schon daraus abgeleitet werden, dass die Ehegatten während einer gewissen Zeit zusammenlebten und intime Beziehungen unterhielten; ein derartiges Verhalten kann auch nur vorgespiegelt sein, um die Behörden zu täuschen (<ref-ruling> E. 2b S. 295; <ref-ruling> E. 2b S. 3, 97 E. 3b S. 101 f.; <ref-ruling> E. 4b S. 420 f.; vgl. <ref-ruling> E. 2c S. 7).
Für die Anwendbarkeit von Art. 7 Abs. 2 ANAG genügt es freilich nicht, dass die Ehe abgeschlossen wurde, um dem ausländischen Ehegatten den Aufenthalt in der Schweiz zu ermöglichen; erforderlich ist vielmehr, dass die eheliche Gemeinschaft nicht wirklich gewollt war. Auf die Motive der Heirat kommt es mit anderen Worten nicht an, sofern der Wille vorhanden ist, eine Lebensgemeinschaft zu begründen (<ref-ruling> E. 3b S. 102 mit Hinweis; vgl. <ref-ruling> E. 1b S. 6).
b) Die Eheleute E._ haben geheiratet, um der Ehefrau ein Anwesenheitsrecht in der Schweiz zu verschaffen.
Der Beschwerdeführer hat sich dahin geäussert, "man" habe ihn gefragt, wie "man" es arrangieren könne, dass E.E._ in die Schweiz einreisen könne. Darauf habe er sich entschlossen, ihr eine Chance zu geben, und sei nach Kavadarci gereist, um sie kennen zu lernen. Die Ehefrau selber hat ausgesagt, sie hätte ihren Mann am 14. Dezember 1997 kennen gelernt. Schon 10 Tage später, am 24. Dezember 1997, erfolgte die Heirat. Dabei waren keine Familienangehörigen anwesend, nicht einmal die Kinder der Ehefrau, und es gab auch kein Hochzeitsfest. Der Ehefrau war es - nach eigener Aussage - gleichgültig, schon nach so kurzer Zeit zu heiraten. Aus Gutmütigkeit, wie sich der Beschwerdeführer ausdrückte, wollte er seiner Frau die Möglichkeit geben, ihre wirtschaftliche Situation zu verbessern; es gehe ihr vor allem darum, hier für ihre drei Kinder Geld zu verdienen.
Zugleich scheint er sich von der Heirat versprochen zu haben, nach seiner Scheidung wieder mit einer Frau zusammenleben zu können. Aus diesen Umständen der Heirat ist zu schliessen, dass der Wunsch für die Ehefrau, in der Schweiz ein Anwesenheitsrecht zu erhalten, überragende Bedeutung für den Heiratsentschluss hatte. Das reicht für die Annahme einer Scheinehe freilich noch nicht aus, sofern die Ehegatten dennoch tatsächlich eine Lebensgemeinschaft eingehen wollten.
c) Dazu ist zunächst festzuhalten, dass die Eheleute, wenn überhaupt, nur sehr kurz zusammengelebt haben, nach Angaben des Beschwerdeführers drei Monate, nach Darstellung seiner Frau zwei Monate. Im Laufe des Verfahrens haben sie wieder eine gemeinsame Wohnung genommen, allerdings mit getrennten Schlafzimmern. Noch einen Monat nach ihrer Rückkehr in die eheliche Wohnung, befanden sich überdies weit mehr persönliche Gegenstände und Kleider der Ehefrau im Zimmer bei ihrem Arbeitgeber als in der ehelichen Wohnung selbst.
Über die beruflichen Verhältnisse ihres Mannes und seine Verwandten weiss die Ehefrau praktisch nichts. Sie ist seiner Mutter und seinen Geschwistern auch nicht vorgestellt worden, obwohl der Beschwerdeführer Kontakt zu ihnen hat.
Auch umgekehrt zeigt der Beschwerdeführer keinerlei Interesse an den Verwandten seiner Frau, er kennt nicht einmal den Namen ihres Bruders, bei dem er sich in Mazedonien aufgehalten haben soll, oder ihres Vaters.
d) Die Ehe ist eingegangen worden, um der Ehefrau den Aufenthalt in der Schweiz zu ermöglichen. Eine wirkliche Lebensgemeinschaft haben die Ehegatten zudem nicht aufgenommen.
Bei dieser Sachlage haben die kantonalen Behörden die Verlängerung der Aufenthaltsbewilligung verweigern dürfen, ohne Bundesrecht zu verletzen.
3.- Die Verwaltungsgerichtsbeschwerde ist demnach als unbegründet abzuweisen.
Bei diesem Ausgang sind die Kosten des bundesgerichtlichen Verfahrens dem Beschwerdeführer aufzuerlegen (Art. 156 Abs. 1 in Verbindung mit Art. 153 und Art. 153a OG). Seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung (Art. 152 OG) kann nicht entsprochen werden, da er es - trotz Aufforderung (Schreiben des Abteilungspräsidenten vom 9. Mai 2000) - unterlassen hat, seine Bedürftigkeit auszuweisen.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3.- Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
4.- Dieses Urteil wird dem Beschwerdeführer, dem Justiz- und Polizeidepartement und dem Verwaltungsgericht des Kantons St. Gallen sowie dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 21. August 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: