Sachverhalt:
A.
Am 9. Mai 2012 klagten C._ Inc. und D._ SA (Klägerinnen, Beschwerdegegnerinnen) beim Obergericht Appenzell Ausserrhoden gegen A._ AG und B._ AG (Beklagte, Beschwerdeführerinnen) mit den folgenden Rechtsbegehren:
"1. Es sei festzustellen, dass der Gebrauch der Schweizer Marke xxx 'Y._', welche von der Beklagten 1 am 12. Mai 2009 für 'Mittel zur Körper- und Schönheitspflege' (Nizza Klassifikation 3) hinterlegt wurde, widerrechtlich ist.
2. Die schweizerische Marke xxx 'Y._', welche von der Beklagten 1 am 12. Mai 2009 für 'Mittel zur Körper- und Schönheitspflege' (Nizza Klassifikation 3) hinterlegt wurde, sei für nichtig zu erklären und das Eidgenössische Institut für Geistiges Eigentum sei anzuweisen, die Marke xxx zu löschen.
3. Den Beklagten 1 und 2 sei zu verbieten, in der Schweiz das Zeichen 'Z._' alleine oder in Verbindung mit dem Zeichen 'Y._' für jegliche Art von Waren, Produkten und/oder Dienstleistungen zu verwenden.
4. Den Beklagten 1 und 2 sei zu verbieten, in der Schweiz die unter der Marke xxx 'Y._' vertriebenen Produkte sowie Produkte mit dem Zeichen 'Z._' und/oder 'Y._' herzustellen, zu benutzen, anzupreisen, zu importieren, zu exportieren, zu lagern, zu verkaufen oder sonstwie in Verkehr zu bringen oder bei entsprechenden Handlungen Dritter in irgendwelcher Weise mitzuwirken.
5. Die Beklagten 1 und 2 seien zu verpflichten, das Zeichen 'Z._' und/oder 'Y._' von sämtlichen bestehenden Produkten zu entfernen sowie die sich in der Schweiz im Handel befindlichen Produkte mit dem Zeichen 'Z._' und/oder 'Y._' zurückzuziehen und sämtliche Verwendungen des Zeichens 'Z._' auf den Webseiten der Beklagten 1 und 2 zu entfernen.
6. Die Beklagten 1 und 2 seien zu verpflichten, sämtliche Lizenznehmer, Abnehmer und/oder Kunden, welche Produkte mit dem Zeichen 'Z._' und/oder 'Y._' oder andere Produkte mit dem Zeichen 'Z._' vertreiben, über die Nichtigkeit der Marke 'Y._' zu informieren und diese aufzufordern, die Marke 'Y._' nicht bzw. nicht weiter zu gebrauchen.
Alles unter Androhung von Busse wegen Ungehorsams gegen amtliche Verfügungen gemäss <ref-law> im Falle der Zuwiderhandlung und unter Kosten- und Entschädigungsfolge zu Lasten der Beklagten 1 und 2."
Die Beklagten beantragten die Abweisung der Klage unter Kosten- Entschädigungsfolge zulasten der Klägerinnen.
B.
Mit Entscheid vom 7. Juni 2016 wies das Obergericht Appenzell Ausserrhoden die Klage vollumfänglich ab (Dispositiv-Ziffer 1). Die Gerichtskosten von Fr. 20'000.-- auferlegte es den Klägerinnen unter solidarischer Haftbarkeit, wobei es den von ihnen geleisteten Kostenvorschuss von Fr. 10'000.-- anrechnete (Dispositiv-Ziffer 2). Zudem verpflichtete es die Klägerinnen solidarisch, die Beklagten für die Kosten ihrer Rechtsvertretung mit insgesamt Fr. 34'026.-- (inkl. Barauslagen und Mehrwertsteuer) zu entschädigen (Dispositiv-Ziffer 3).
C.
Mit Beschwerde in Zivilsachen beantragen die Beklagten, es sei Dispositiv-Ziffer 3 des Entscheids des Obergerichts Appenzell Ausserrhoden vom 7. Juni 2016 aufzuheben und es seien die Beschwerdegegnerinnen solidarisch zur Zahlung einer Parteientschädigung von insgesamt Fr. 109'353.55 (inkl. Barauslagen und Mehrwertsteuer) zu verpflichten. Eventualiter sei die Sache zur Neufestlegung der Parteientschädigung an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerinnen beantragen die Abweisung der Beschwerde. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.
Die Beschwerdeführerinnen haben dem Bundesgericht eine Replik, die Beschwerdegegnerinnen haben ihm eine Duplik eingereicht.

Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-law>; <ref-ruling> E. 2.1 mit Hinweisen).
1.1. Die Beschwerde betrifft eine Zivilrechtsstreitigkeit im Zusammenhang mit geistigem Eigentum. Dafür sieht ein Bundesgesetz (<ref-law> [SR 272]) eine einzige kantonale Instanz vor (<ref-law>). Die Beschwerde in Zivilsachen, die sich gegen einen Endentscheid (<ref-law>) richtet, ist demnach unabhängig vom Streitwert zulässig (<ref-law>). Die Beschwerdeführerinnen sind mit ihren Anträgen zur Höhe der Parteientschädigung unterlegen (<ref-law>) und die Beschwerdefrist ist eingehalten (<ref-law>).
Auf die Beschwerde in Zivilsachen ist somit - unter Vorbehalt einer rechtsgenügenden Begründung (Art. 42 Abs. 2 und <ref-law>) - einzutreten.
1.2. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen oder eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Mit Blick auf die Begründungspflicht der beschwerdeführenden Partei (Art. 42 Abs. 1 und 2 BGG) behandelt es aber grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind; es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 2 S. 116; <ref-ruling> E. 1.3; <ref-ruling> E. 1.4). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>).
Unerlässlich ist im Hinblick auf Art. 42 Abs. 2 und <ref-law>, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Rechtsverletzung liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die sie im vorinstanzlichen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2 S. 89, 115 E. 2 S. 116). Die Begründung hat ferner in der Beschwerdeschrift selbst zu erfolgen und der blosse Verweis auf Ausführungen in anderen Rechtsschriften oder auf die Akten reicht nicht aus. Für die Beschwerdeantwort gelten dieselben Begründungsanforderungen (<ref-ruling> E. 2 S. 116).
1.3. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den streitgegenständlichen Lebenssachverhalt als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (<ref-ruling> E. 1.3.1 mit Hinweisen). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 117; <ref-ruling> E. 1.5). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein können (<ref-law>).
Für eine Kritik am festgestellten Sachverhalt gilt das strenge Rügeprinzip von <ref-law> (<ref-ruling> E. 2.3 S. 266 mit Hinweisen). Die Partei, welche die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 1.3.1 S. 18 mit Hinweisen). Wenn sie den Sachverhalt ergänzen will, hat sie zudem mit präzisen Aktenhinweisen darzulegen, dass sie entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (<ref-ruling> E. 2 S. 90). Genügt die Kritik diesen Anforderungen nicht, können Vorbringen mit Bezug auf einen Sachverhalt, der vom angefochtenen Entscheid abweicht, nicht berücksichtigt werden (<ref-ruling> E. 1.3.1 S. 18).
1.4. Die Beschwerde ist innert der Beschwerdefrist vollständig begründet einzureichen (<ref-law>). Kommt es zu einem zweiten Schriftenwechsel, darf die beschwerdeführende Partei die Replik nicht dazu verwenden, ihre Beschwerde zu ergänzen oder zu verbessern (vgl. <ref-ruling> E. 3.3.4). Die Replik ist nur zu Darlegungen zu verwenden, zu denen die Ausführungen in der Vernehmlassung eines anderen Verfahrensbeteiligten Anlass geben (vgl. <ref-ruling> E. 2.2).
Soweit die Beschwerdeführerinnen in ihrer Replik darüber hinausgehen, können ihre Ausführungen nicht berücksichtigt werden.
1.5. Mit ihren Vorbringen zur vorinstanzlichen Streitwertbestimmung verkennen die Beschwerdeführerinnen diese Grundsätze über weite Strecken, indem sie verschiedentlich von den tatsächlichen Feststellungen der Vorinstanz abweichen oder diese erweitern, ohne substanziiert Ausnahmen von der Sachverhaltsbindung geltend zu machen. So behaupten sie etwa, durch die Löschung der strittigen Marke entstehe der Beschwerdeführerin 1 ein "immenser" Schaden und die Löschung ziehe bedeutende wirtschaftliche Auswirkungen auch im Ausland nach sich. Abgesehen davon wären ihre pauschal gehaltenen Behauptungen nicht genügend konkret für eine abweichende Streitwertberechnung. Die entsprechenden Ausführungen haben ebenso unbeachtet zu bleiben wie die Vorbringen in der Beschwerde dazu, welchen Teil des Sortiments ihre Linie "Y._" abdecke bzw. wie viele Produkte, Verpackungen und Werbematerialien hergestellt worden seien, welche die Marke aufweisen, oder welchen Imageverlust ein Rückruf der Produkte verursacht hätte. Sie zeigen nicht mit Aktenhinweisen auf, dass sie entsprechende Vorbringen bereits bei der Vorinstanz prozesskonform eingebracht hätten. Die entsprechenden Ausführungen haben unbeachtet zu bleiben.
Neu und damit unbeachtlich sind die Ausführungen in der Beschwerde, mit denen sich die Beschwerdeführerinnen im Zusammenhang mit dem Rechtsschutzinteresse an der Gutheissung von Antrags-Ziffer 1 der Klage zu den damit verbundenen wirtschaftlichen Vorteilen für die Beschwerdegegnerinnen äussern und gestützt darauf nunmehr vor Bundesgericht geltend machen, bereits dieses Rechtsbegehren würde einen Streitwert von mindestens Fr. 1 Mio. rechtfertigen.
2.
Die Beschwerdeführerinnen rügen, die Vorinstanz habe bei der Bestimmung des dem Kostenentscheid zugrunde gelegten Streitwerts <ref-law> verletzt und den Streitwert willkürlich (<ref-law>) festgelegt.
2.1. Die Vorinstanz wies darauf hin, dass die Beschwerdegegnerinnen von einem Streitwert von insgesamt Fr. 50'000.-- bis Fr. 100'000.-- ausgingen, während sich nach den Beschwerdeführerinnen der Streitwert der Nichtigkeitsklage in Bezug auf ihre Marke auf ca. Fr. 800'000.-- belaufe und die Wertbeeinträchtigung der Marke "Z._" mit Fr. 100'000.-- zu veranschlagen sei; ein weiterer Betrag rechtfertige sich nach Ansicht der Beschwerdeführerinnen gestützt auf das UWG, weshalb insgesamt von einem Streitwert von rund Fr. 1 Mio. auszugehen sei. Die Vorinstanz erwog, der Streitwert in Angelegenheiten, die sich mit dem Bestand oder der Verletzung von Immaterialgüterrechten befassen, sei schwer bestimmbar. In der Lehre werde deshalb vorgeschlagen, es seien aufgrund von Erfahrungswerten über den Wert der umstrittenen Rechte Richtlinien oder Eckdaten aufzustellen, die vermutungsweise der Schätzung des prozessual massgebenden Streitwerts zugrunde gelegt werden könnten. In diesem Sinne werde gestützt auf die Erfahrungen der Praxis angenommen, dass der Streitwert zwischen Fr. 50'000.-- und Fr. 100'000.-- liege, wenn es um eher unbedeutende Zeichen gehe; der Streitwert betrage Fr. 500'000.-- bis Fr. 1 Mio., sofern erhebliche Werte dahinter stünden (Umsatz, Werbung etc.) und belaufe sich auf mehr als Fr. 1 Mio. bei sehr bekannten, wenn nicht berühmten Klagemarken, wobei dann auch eine erhebliche Verletzungshandlung zur Diskussion stehen müsse. Massgeblicher Zeitpunkt für die Bestimmung des Streitwerts sei der Zeitpunkt der Klageeinreichung beim Gericht. Allgemein gelte die Regel, dass über Streitwertfragen keine Beweise zu erheben seien; der Prozess solle nicht durch ein langwieriges Verfahren über solche Punkte belastet werden.
Auszugehen sei im konkreten Fall vom Wert der Marke der Beschwerdegegnerinnen, also "Y._", da das Unterlassungsinteresse der Beschwerdeführerinnen nicht grösser sein könne als der Wert der beklagtischen Marke. Diesen habe der Rechtsvertreter der Beschwerdeführerinnen nicht konkret (d.h. aufgrund von Umsatzzahlen etc.) dargelegt. Zu beachten sei jedoch, dass die Marke "Y._" erst seit wenigen Jahren existiere und die strittigen Marken weit voneinander entfernt seien, so dass die Gefahr einer Verwässerung klein sei, wie in der weiteren Begründung noch dargelegt werde. Von einem völlig unbedeutenden Zeichen könne jedoch ebenfalls nicht die Rede sein; der Streitwert sei deshalb an der Obergrenze für den bestrittenen Bestand solcher Zeichen, also bei Fr. 100'000.--, festzulegen.
2.2. Nach <ref-law> wird der Streitwert durch das Rechtsbegehren bestimmt. Bei einfacher Streitgenossenschaft und Klagenhäufung werden die geltend gemachten Ansprüche zusammengerechnet, sofern sie sich nicht gegenseitig ausschliessen (<ref-law>). Lautet das Rechtsbegehren - wie hier - nicht auf eine bestimmte Geldsumme, so setzt das Gericht den Streitwert fest, sofern sich die Parteien darüber nicht einigen oder ihre Angaben offensichtlich unrichtig sind (<ref-law>). Die gerichtliche Schätzung nach objektiven Kriterien im Rahmen der Festsetzung der Prozesskosten, deren Tarife sich nach kantonalem Recht richten (<ref-law>), ist im Hinblick auf die Kognition des Bundesgerichts vergleichbar mit der ermessensweisen Schadenschätzung nach <ref-law> (Urteil 4A_45/2013 vom 6. Juni 2013 E. 4.2 mit Hinweisen). Diese beruht auf Tatbestandsermessen, gehört mithin zur Feststellung des Sachverhalts (<ref-ruling> E. 5.1 S. 364; <ref-ruling> E. 2b/aa S. 277; <ref-ruling> E. 2c/bb S. 65, 219 E. 3b S. 222). Es kann daher nur gerügt werden, der angefochtene Entscheid über die Höhe der Prozesskosten sei offensichtlich unhaltbar und damit willkürlich (<ref-law>). Eine derartige Rüge ist nach Massgabe von <ref-law> zu begründen (<ref-ruling> E. 1.4.3 mit Hinweisen).
2.3.
2.3.1. Entgegen dem, was die Beschwerdeführerinnen anzunehmen scheinen, ist der Vorinstanz nicht etwa entgangen, dass neben dem Bestand ihrer Marke auch weitere Rechtsbegehren zu beurteilen waren, die bei der Bestimmung des Streitwerts zu berücksichtigen sind. So hat sie namentlich das Unterlassungsinteresse der Beschwerdegegnerinnen als massgeblichen Gesichtspunkt bei der Streitwertbestimmung erachtet. Sie hat daher nicht etwa einzelne Rechtsbegehren unberücksichtigt gelassen, sondern den Streitwert unter Hinweis auf die Schwierigkeiten der Streitwertbemessung bei Bestandes- und Verletzungsklagen im Immaterialgüterrecht als Ganzes geschätzt, nachdem sich die Parteien nicht einigen konnten. Damit hat die Vorinstanz nicht verkannt, dass verschiedene Rechtsbegehren vorliegen und die mittels Klagenhäufung geltend gemachten Ansprüche grundsätzlich zusammenzurechnen sind, soweit sie sich nicht gegenseitig ausschliessen.
Die Rüge, es liege eine Verletzung von <ref-law> vor, ist unbegründet.
2.3.2. Auch die Beschwerdeführerinnen haben im vorinstanzlichen Verfahren mit ihren Vorbringen zum Streitwert im Wesentlichen auf den Wert ihrer Marke abgestellt, diesen jedoch höher als die Vorinstanz veranschlagt, wobei sie zusätzlich einen Wert von Fr. 100'000.-- für die Schädigung der Marke der Beschwerdegegnerinnen und einen weiteren Betrag von Fr. 100'000.-- "gestützt auf das UWG" geltend machten. Soweit sie sich nunmehr vor Bundesgericht zu jedem einzelnen Rechtsbegehren der Beschwerdegegnerinnen äussern und jedem Individualbegehren einen eigenen Wert beimessen wollen, sind ihre Vorbringen hinsichtlich des Klagebegehrens Ziffer 1 nach <ref-law> unzulässig und im Übrigen weitgehend appellatorisch (siehe vorn E. 1.5). Unbeachtlich sind insbesondere ihre Ausführungen zu den Klagebegehren Ziffern 5 und 6, mit denen sie sich durchgehend auf Sachverhaltselemente zu dem durch den beantragten Rückruf und die Vernichtung von Produkten sowie Werbemitteln erlittenen Schaden wie auch zum Ausmass eines angeblichen Imageverlusts stützen, die sich dem angefochtenen Entscheid nicht entnehmen lassen.
Im Zusammenhang mit dem Klagebegehren Ziffer 2 stellen die Beschwerdeführerinnen die vorinstanzliche Schätzung des Werts der Marke "Y._" in Frage und stellen sich auf den Standpunkt, dieser betrage entgegen dem angefochtenen Entscheid nicht bloss Fr. 100'000.--, sondern mindestens Fr. 800'000.--. Dabei werfen sie der Vorinstanz zu Unrecht vor, sie habe die bisherige Gebrauchsdauer der Marke ausser Acht gelassen. Ebenso wenig ist ihr entgangen, dass die Beschwerdeführerinnen im vorinstanzlichen Verfahren eine internationale Anmeldung für 26 Länder ins Feld geführt hatten. Weder hinsichtlich der Bewertung der Marke noch in Bezug auf die Berücksichtigung einer internationalen Anmeldung (dazu etwa MARKUS R. FRICK, in: Basler Kommentar, Markenschutzgesetz/Wappenschutzgesetz, 3. Aufl. 2017, N. 85 Vor Art. 51a-60 MSchG) vermögen die Beschwerdeführerinnen anerkannte Grundsätze der Streitwertbestimmung aufzuzeigen, die von der Vorinstanz willkürlich angewendet worden wären.
Da der Streitwert in Angelegenheiten, die sich mit dem Bestand oder der Verletzung von Immaterialgüterrechten befassen, nicht leicht zu bestimmen ist, hat die Vorinstanz willkürfrei auf in der Praxis verwendete Erfahrungswerte abgestellt, nach denen der Streitwert zwischen Fr. 50'000.-- und Fr. 100'000.-- liegt, wenn es um eher unbedeutende Zeichen geht (vgl. <ref-ruling> E. 3.3 mit Hinweisen). Sie wies ausserdem darauf hin, dass der Streitwert Fr. 500'000.-- bis Fr. 1 Mio. betrage, sofern erhebliche Werte dahinter stünden (Umsatz, Werbung etc.), und er belaufe sich auf mehr als Fr. 1 Mio. bei sehr bekannten, wenn nicht berühmten Marken (vgl. etwa auch FRICK, a.a.O., N. 84 Vor Art. 51a-60 MSchG). Die Beschwerdeführerinnen bestreiten zwar, dass es sich bei "Y._" um eine eher unbedeutende Marke handelt, legen mit ihren Ausführungen jedoch nicht dar, inwiefern die vorinstanzliche Schätzung offensichtlich unhaltbar wäre, nachdem sie bereits im vorinstanzlichen Verfahren auf konkrete Angaben zur Bewertung verzichtet hatten. Auch mit dem blossen Hinweis darauf, dass "von den beteiligten Anwälten ein aussergewöhnlicher Aufwand von je ca. 250 Stunden" betrieben worden sei, wird keine willkürliche Bestimmung des Streitwerts aufgezeigt.
Auch mit ihrem Vorbringen, dass sich die Rechtsbegehren Ziffern 3 und 4 sowohl auf Marken- als auch auf Lauterkeitsrecht stützen, zeigen die Beschwerdeführerinnen keine Bundesrechtsverletzung bei der Bestimmung des Streitwerts auf. Ebenso wenig vermögen sie mit dem nicht weiter begründeten Standpunkt, "Ansprüche aus UWG" führten zwingend zu einem zusätzlichen Streitwert von mindestens Fr. 100'000.--, Willkür bei der vorinstanzlichen Streitwertschätzung aufzuzeigen.
Die Rüge, die Vorinstanz habe den dem Kostenentscheid zugrunde gelegten Streitwert willkürlich bestimmt, erweist sich als unbegründet. Entsprechend gehen auch die Berechnungen der geltend gemachten Parteientschädigung in der Beschwerdeschrift ins Leere, die sich auf einen höheren Streitwert stützen.
3.
Die Beschwerdeführerinnen bringen weiter vor, die Vorinstanz habe die Parteientschädigung willkürlich festgesetzt.
3.1. Die Vorinstanz führte zu den Entschädigungsfolgen aus, dass sie den Streitwert im vorliegenden Verfahren auf Fr. 100'000.-- festgelegt habe. Es bestehe somit kein Grund, die Parteientschädigung für die Beschwerdeführerinnen nach Zeitaufwand und nicht gemäss ständiger Praxis nach Streitwert zu bemessen; dabei verwies sie auf Art. 18 Abs. 1 der kantonalen Verordnung vom 14. März 1995 über den Anwaltstarif (Anwaltstarif; BGS 145.53). Sie erwog sodann, bei einem Streitwert von Fr. 100'000.-- betrage das mittlere Honorar nach Art. 9 Abs. 2 lit. d Anwaltstarif Fr. 12'400.--. Dazu könne nach Art. 11 Abs. 1 in Verbindung mit Abs. 2 lit. a ein Zuschlag von einem Viertel, also Fr. 3'100.--, gewährt werden. Weil sich das Verfahren tatsächlich sehr komplex gestaltet habe, ein Beweisverfahren initiiert und zwischen den Parteien auch Vergleichsverhandlungen geführt worden seien, erschienen zudem Zuschläge gestützt auf Art. 12 Abs. 1 lit. a, b, c und e Anwaltstarif als gerechtfertigt. Diese seien insgesamt auf 100 %, d.h. Fr. 12'400.--, festzulegen (Art. 12 Abs. 2 Anwaltstarif). Dazu kämen Fr. 718.20 für 1'026 Kopien (Art. 22 Abs. 2 Anwaltstarif), Fr. 187.30 für Porti und Telefonspesen, Fr. 2'700.-- für Übersetzungen sowie Fr. 2'520.40 für die Mehrwertsteuer von 8 %. Insgesamt hätten die Beschwerdegegnerinnen die Beschwerdeführerinnen also mit Fr. 34'026.-- zu entschädigen.
3.2. Die Beschwerdeführerinnen werfen der Vorinstanz zunächst vor, sie habe keinerlei Gründe dafür angegeben, weshalb nicht von einer streitwertabhängigen Berechnung der Parteientschädigung habe abgewichen werden können, obwohl dies von ihnen geltend gemacht worden sei. Sie legen jedoch in keiner Weise dar, inwiefern ihnen die Begründung des angefochtenen Entscheids verunmöglicht hätte, diesen sachgerecht anzufechten (vgl. <ref-ruling> E. 6.2 S. 274; <ref-ruling> E. 2.2.1 S. 188; <ref-ruling> E. 4.1 S. 88; je mit Hinweisen). Ebenso wenig vermögen sie in diesem Zusammenhang aufzuzeigen, dass die Vorinstanz in Willkür verfallen wäre, indem sie die Parteientschädigung nach Art. 9 Abs. 2 Anwaltstarif anhand des Streitwerts festlegte, zumal Art. 8 vorsieht, dass die Bemessung nach Streitwert in Zivilprozessen und bei Verwaltungsgerichtsklagen "mit bestimmtem oder bestimmbarem Streitwert" zur Anwendung kommt. Daran ändert auch der Hinweis in der Beschwerde auf Art. 18 Abs. 1 lit. a Anwaltstarif nichts, wonach die Bemessung nach Zeitaufwand in Zivilverfahren zur Anwendung kommt, "wenn ein Streitwert nicht oder nur schwierig zu ermitteln ist [...]". Legt das Gericht den Streitwert - wie hier - aufgrund einer Schätzung fest, so setzt dies voraus, dass dieser zumindest bestimmbar ist (Art. 8 Anwaltstarif) und es leuchtet entgegen der in der Beschwerde vertretenen Ansicht nicht ohne Weiteres ein, dass die Parteientschädigung in einem solchen Fall ungeachtet des tatsächlich ermittelten Streitwerts zwingend nach Zeitaufwand zu bemessen wäre (Art. 18 Abs. 1 lit. a Anwaltstarif), nur weil sich die Ermittlung des Streitwerts als schwierig erwies.
Der Vorwurf der willkürlichen Anwendung des kantonalen Anwaltstarifs erweist sich insoweit als unbegründet.
3.3. Die Beschwerdeführerinnen machen sodann vergeblich geltend, die Vorinstanz habe Art. 2 Abs. 3 Anwaltstarif willkürlich angewendet, auf den sie sich im kantonalen Verfahren berufen hatten und der Abweichungen von den tariflichen Entschädigungen bei einem "krassen Missverhältnis zu den geleisteten Bemühungen" vorsieht. Mit dem blossen Vorbringen, "angesichts der vielen geleisteten Stunden des Rechtsvertreters und dem Zugeständnis der Vorinstanz, dass es sich um eine äusserst komplizierte Rechtslage mit fremdsprachigen Akten, mehreren Parteien und grundsätzlicher Bedeutung" gehandelt habe und dem Hinweis auf die "Bemühungslisten beider involvierter Rechtsvertreter" zeigen sie keine willkürliche Anwendung der erwähnten Verordnungsbestimmung auf, zumal die Vorinstanz den Besonderheiten der Streitsache mit den Zuschlägen nach Art. 11 Abs. 2 lit. a und Art. 12 Abs. 1 lit. a-c sowie e Anwaltstarif Rechnung getragen hat.
3.4.
3.4.1. Die Beschwerdeführerinnen machen schliesslich subsubeventualiter geltend, die Vorinstanz habe sich bei der Berechnung der Zuschläge gemäss Art. 12 Abs. 1 lit. a-c und e Anwaltstarif geirrt und habe somit willkürlich gehandelt. Sie räume nämlich einen Zuschlag von 100 % ein, berechne diesen jedoch nach dem mittleren Honorar statt nach dem Grundhonorar, wie dies nach Art. 12 Abs. 2 geboten wäre. Eine korrekte Berechnung des Zuschlags würde eine um 3'100.--, zuzüglich Fr. 248.-- Mehrwertsteuer, erhöhte Parteientschädigung ergeben.
3.4.2. Die Rüge erweist sich als begründet. Art. 12 Abs. 2 Anwaltstarif sieht vor, dass die Zuschläge nach dieser Bestimmung auf dem Grundhonorar (Art. 11) - und nicht etwa auf dem mittleren Honorar (Art. 9) - berechnet werden. Die Vorinstanz berechnete diesen Zuschlag jedoch fälschlicherweise auf dem mittleren Honorar von Fr. 12'400.-- anstatt auf dem als Grundhonorar festgelegten Betrag von Fr. 15'500.-- (Fr. 12'400 plus Fr. 3'100.--). Sowohl der Wortlaut als auch die Systematik der kantonalen Verordnung sind in dieser Hinsicht eindeutig und lassen keine andere Berechnung zu. Es ist daher von einem offensichtlichen Versehen auszugehen.
Wird der Zuschlag von 100 % nach Art. 12 auf dem Grundhonorar von Fr. 15'500.-- berechnet, ergibt sich eine Entschädigung von insgesamt Fr. 31'000.--. Werden die festgelegten Beträge von Fr. 718.20 für Kopien, Fr. 187.30 für Porti und Telefonspesen, Fr. 2'700.-- für Übersetzungen sowie die Mehrwertsteuer von 8 % (auf Fr. 34'605.50, also Fr. 2'768.45) hinzugerechnet, ergibt sich eine Parteientschädigung von insgesamt Fr. 37'373.95.--.
Entsprechend ist Dispositiv-Ziffer 3 des angefochtenen Entscheids aufzuheben und wie folgt neu zu fassen:
"Die Klägerinnen 1 und 2 werden solidarisch verpflichtet, die Beklagten 1 und 2 für die Kosten ihrer Rechtsvertretung mit insgesamt Fr. 37'373.95 (inkl. Barauslagen und Mehrwertsteuer) zu entschädigen."
4.
Da die Beschwerde lediglich in einem äusserst geringen Betrag im Vergleich zur beantragten Summe durchdringt, werden die Beschwerdeführerinnen trotz teilweiser Gutheissung der Beschwerde kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie Art. 68 Abs. 1 und 4 BGG).

Demnach erkennt das Bundesgericht:
1.
In teilweiser Gutheissung der Beschwerde wird Dispositiv-Ziffer 3 des Urteils des Obergerichts Appenzell Ausserrhoden vom 7. Juni 2016 aufgehoben und wie folgt neu gefasst:
"Die Klägerinnen 1 und 2 werden solidarisch verpflichtet, die Beklagten 1 und 2 für die Kosten ihrer Rechtsvertretung mit insgesamt Fr. 37'373.95 (inkl. Barauslagen und Mehrwertsteuer) zu entschädigen."
Im Übrigen wird die Beschwerde abgewiesen.
2.
Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführerinnen (unter solidarischer Haftung und intern je zur Hälfte) auferlegt.
3.
Die Beschwerdeführerinnen haben die Beschwerdegegnerinnen für das bundesgerichtliche Verfahren (unter solidarischer Haftbarkeit und intern je zur Hälfte) mit insgesamt Fr. 5'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht Appenzell Ausserrhoden, 1. Abteilung, schriftlich mitgeteilt.
Lausanne, 29. Mai 2017
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Leemann