Sachverhalt:
A.
A._ (Kläger, Beschwerdeführer) war vom 13. August 2007 bis zum 31. März 2008 bei der X._ AG mit Sitz in Liechtenstein (Beklagte, Beschwerdegegnerin) bei der Zweigniederlassung Y._ Oberriet SG als technischer Leiter angestellt. Am 7. April 2008 mahnte er die Arbeitgeberin, ihm innerhalb von sieben Tagen den ausstehenden Lohn inkl. Überzeit, eine korrekte Abrechnung inkl. Überstunden und ein unkodiertes Arbeitszeugnis zukommen zu lassen. Als die Zweigniederlassung diesen Forderungen nicht nachkam, gelangte er an die Schlichtungsstelle für Arbeitsverhältnisse. Der Vorstand blieb unvermittelt.
B.
Am 23. Dezember 2009 reichte der Kläger beim Kreisgericht Rheintal Klage ein. Er verlangte im Wesentlichen, die Beklagte zu verpflichten, ihm eine nach Durchführung des Beweisverfahrens zu beziffernde Forderung zu bezahlen und ein textmässig vorgegebenes Zeugnis auszustellen. Die Beklagte beantragte, das Verfahren gemäss <ref-law> einzustellen, die Klage auf Lohnforderung abzuweisen und das vom Kläger vorgeschlagene Zeugnis hinsichtlich eines Abschnittes anzupassen. Widerklageweise verlangte sie eine Entschädigung im Sinne von <ref-law> von Fr. 5'725.-- sowie die Rückzahlung zu Unrecht bezahlten Lohns für den Monat März 2008 von Fr. 2'451.35. In der Duplik stellte sie zudem ein Sistierungsbegehren, bis über die Verfahrenseinstellung nach <ref-law> rechtskräftig entschieden sei. In der Folge wurde das Verfahren betreffend die Widerklage am 4. Oktober 2010 gestützt auf <ref-law> bis auf weiteres sistiert und getrennt vom hier zu beurteilenden Klageverfahren durchgeführt. Mit Eingabe vom 12. September 2011 bezifferte der Kläger seine Klageforderung auf Fr. 35'848.50. Am 11. Januar 2012 sprach das Kreisgericht dem Kläger Fr. 22'742.65 nebst Zins zu und verpflichtete die Beklagte, binnen 10 Tagen nach Eintritt der Rechtskraft des Entscheides das vom Kläger beantragte Zeugnis auszustellen. Die Entscheidgebühr von Fr. 6'000.-- auferlegte es der Beklagten, erstattete dem Kläger die Einschreibgebühr von Fr. 1'300.-- zurück und sprach ihm eine Entschädigung für seine Parteikosten von Fr. 14'990.65 zu.
C.
Die Beklagte erhob gegen das Urteil des Kreisgerichts beim Kantonsgericht des Kantons St. Gallen Berufung und beantragte, den Entscheid des Kreisgerichts aufzuheben und die Klage kostenfällig abzuweisen. Die Kosten sollten zu Lasten des Klägers gehen. Der Kläger schloss im Wesentlichen auf Abweisung der Berufung. Mit Entscheid vom 4. Dezember 2012 sprach das Kantonsgericht dem Kläger lediglich Fr. 20'917.40 nebst Zins zu und wies im Übrigen die Berufung ab (Dispositivziffer 1). Die erstinstanzliche Entscheidgebühr von Fr. 6'000.-- auferlegte es zu 3/5 der Beklagten und zu 2/5 dem Kläger (Dispositivziffer 2), die zweitinstanzliche von Fr. 4'000.-- der Beklagten zu 9/10 und dem Kläger zu 1/10 (Dispositivziffer 3). Dabei rechnete es die Einschreibgebühr und den geleisteten Kostenvorschuss an. Sodann hatte die Beklagte den Kläger für dessen Parteikosten im Verfahren vor beiden Instanzen mit Fr. 4'678.55 zu entschädigen (Dispositivziffer 4).
D.
Mit Beschwerde in Zivilsachen beantragt der Kläger dem Bundesgericht im Wesentlichen, die Dispositivziffern 2, 3 und 4 des kantonsgerichtlichen Entscheides aufzuheben, die Beschwerdegegnerin zur Tragung der erst- und zweitinstanzlichen Entscheidgebühren zu verpflichten und ihn für das kantonale Verfahren insgesamt mit Fr. 17'197.80 (eventuell nach richterlichem Ermessen) zu entschädigen. Die Beschwerdegegnerin schliesst auf kostenfällige Abweisung der Beschwerde, während das Kantonsgericht auf Vernehmlassung verzichtet. Obwohl kein zweiter Schriftenwechsel angeordnet wurde, haben die Parteien eine Replik und eine Duplik eingereicht.

Erwägungen:
1.
Zu beurteilen ist ein arbeitsrechtlicher Fall, in dem die vor der Vorinstanz streitige Summe Fr. 15'000.-- übersteigt. Die Beschwerde in Zivilsachen steht demnach offen (<ref-law>), auch wenn, wie hier, nur die Kosten- und Entschädigungsfolgen angefochten werden (<ref-ruling> E. 1.2).
2.
Die Vorinstanz hielt fest, der Beschwerdeführer habe seine Klageforderung im erstinstanzlichen Verfahren auf Fr. 35'848.50 beziffert. Darin sei jedoch der Streitwert für die Berichtigung des Arbeitszeugnisses nicht erhalten. Da lediglich die Abänderung des dritten Abschnittes des Zeugnisses strittig sei, setzte die Vorinstanz den Streitwert für das Zeugnis auf einen halben Monatslohn (Fr. 2'862.50) fest. Damit habe der Streitwert im erstinstanzlichen Verfahren Fr. 38'711.-- betragen. Dem Beschwerdeführer würden Fr. 23'779.90 (Fr. 19'417.40 Überstunden, Fr. 2'862.50 Zeugnisberichtigung und Fr. 1'500.-- Kaufpreis Kärcher) zugesprochen oder rund 60 %. Dies rechtfertige, die Prozesskosten der Beschwerdegegnerin zu 3/5 und dem Beschwerdeführer zu 2/5 aufzuerlegen. Für das Berufungsverfahren ging die Vorinstanz von einem Streitwert von Fr. 25'605.15 aus (Fr. 22'742.65 erstinstanzlich zugesprochener Betrag und Fr. 2'862.50 Zeugnisberichtigung). Mit Fr. 23'779.90 würden dem Beschwerdeführer rund 92 % dieses Betrages zugesprochen, was eine Kostenverteilung zu 9/10 zu Lasten der Beschwerdegegnerin und zu 1/10 zu Lasten des Beschwerdeführers rechtfertige. Die Vorinstanz setzte sodann die volle Parteientschädigung gestützt auf den von ihr angenommenen Streitwert für das erstinstanzliche Verfahren auf Fr. 12'163.05 und für das zweitinstanzliche auf Fr. 2'807.45 fest und sprach dem Beschwerdeführer gestützt auf den der Kostenverteilung zu Grunde gelegten Umfang des Obsiegens für die erste Instanz 1/5 (Fr. 2'432.60) und für die zweite Instanz 8/10 (Fr. 2'245.95) als Parteientschädigung zu.
3.
Das erstinstanzliche Verfahren richtete sich nach dem kantonalen Zivilprozessgesetz vom 20. Dezember 1990 (ZPO/SG), während im kantonalen Rechtsmittelverfahren die Schweizerische Zivilprozessordnung (ZPO) anzuwenden war (Art. 404 Abs. 1 und Art. 405 Abs. 1 ZPO). Die Vorinstanz hatte indessen im Berufungsverfahren den erstinstanzlichen Entscheid nicht nur im Kostenpunkt zu überprüfen, sondern sie hat mit der Gutheissung der Berufung über die im Streit liegenden Forderungen materiell neu entschieden. Damit hatte sie nach <ref-law> auch über die Prozesskosten des erstinstanzlichen Verfahrens neu zu entscheiden. In dieser Situation ist auch über die erstinstanzlichen Prozesskosten nach den Regeln der ZPO zu entscheiden (Urteil des Bundesgerichts 4A_17/2013 vom 13. Mai 2013 E. 4.1), deren Anwendung das Bundesgericht frei prüft (<ref-law>). Dabei ist es aber unter Vorbehalt von Art. 97 Abs. 1 und <ref-law> an die tatsächlichen Feststellungen im angefochtenen Entscheid gebunden (<ref-law>). Die Festsetzung der Tarife für die Prozesskosten bleibt dagegen auch unter Geltung der eidgenössischen ZPO dem kantonalen Recht, hier der Honorarordnung für Rechtsanwälte und Rechtsagenten vom 22. April 1994 (HonO/SG; sGS 963.75), vorbehalten (<ref-law>). Dieses überprüft das Bundesgericht nur auf Willkür (<ref-ruling> E. 2.4 S. 249; <ref-ruling> E. 1.2 S. 382 f.).
4.
Der Beschwerdeführer rügt zunächst, die Vorinstanz habe zu Unrecht bloss den Streitwert für eine Berichtigung des Zeugnisses berücksichtigt. Sie habe übersehen, dass die Ausstellung eines Zeugnisses eingeklagt gewesen sei und die Beschwerdegegnerin nie ein Zeugnis zugestellt habe. Daher sei der Streitwert für das vollständige Zeugnis massgebend, der nach Auffassung des Beschwerdeführers einen vollen Monatslohn (Fr. 5'725.--) betrage. Auch im Berufungsverfahren sei der höhere Streitwert zu beachten, da die Beschwerdegegnerin den erstinstanzlichen Entscheid vollumfänglich angefochten habe. Dies sei auch für das Mass des Obsiegens vor beiden kantonalen Instanzen zu berücksichtigen.
4.1. Grundsätzlich wird der Streitwert durch das Rechtsbegehren bestimmt (<ref-law>) und gilt bei Anerkennung der Klage die beklagte Partei als unterliegend (<ref-law>). Der Beschwerdeführer hat der Beschwerdegegnerin Frist angesetzt, um ihm ein Zeugnis auszustellen. Dass sie ihm vor der Klageeinreichung ein Zeugnis ausgestellt oder dies zumindest angeboten hätte, ist nicht festgestellt. Wenn die Beschwerdegegnerin in der Klageantwort das vom Beschwerdeführer vorgeschlagene Zeugnis nur in einem Absatz beanstandet, liegt bezüglich der restlichen Absätze eine Klageanerkennung vor.
4.2. Lautet das Rechtsbegehren 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>). Besteht zwischen den Parteien keine Einigkeit, so liegt die Bestimmung des Streitwertes im Ermessen des Sachgerichts ( STEIN-WIGGER, in: Kommentar zur Schweizerischen Zivilprozessordnung [ZPO], Sutter-Somm und andere [Hrsg.], 2. Aufl. 2013, N. 25 zu <ref-law>; vgl. auch Urteil des Bundesgerichts 4P.208/2001 vom 21. November 2001 E. 3b). Dieses hat den Streitwert nach einem objektiven Massstab zu schätzen ( BEATRICE VAN DE GRAAF, in: ZPO: Schweizerische Zivilprozessordnung, Oberhammer [Hrsg.], 2010, N. 9 zu <ref-law>; vgl. auch BEAT RUDIN, in: Basler Kommentar, Bundesgerichtsgesetz, 2. Aufl. 2011, N. 47 zu <ref-law>). Die Schätzung nach objektiven Kriterien ist im Hinblick auf die Kognition des Bundesgerichts vergleichbar mit der ermessensweisen Schadenschätzung nach <ref-law>. Diese beruht - von der ausnahmsweisen Berücksichtigung abstrakter Erfahrungssätze abgesehen - auf Tatbestandsermessen, gehört mithin zur Feststellung des Sachverhalts (<ref-ruling> E. 5.1 S. 364; <ref-ruling> E. 2c/bb S. 65). Es kann daher nur gerügt werden, der angefochtene Entscheid 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 S. 254 f. mit Hinweisen).
4.3. Nach der Rechtsprechung des Bundesgerichts kann der Wert eines Arbeitszeugnisses nicht losgelöst vom konkreten Fall auf einen Bruchteil oder ein Mehrfaches des Monatslohns festgesetzt werden (Urteil des Bundesgerichts 8C_151/2010 vom 31. August 2010 E. 2.8, teilw. publ. in: ARV 2010 S. 267). Wie wichtig das Zeugnis objektiv ist, hängt von der Situation auf dem Arbeitsmarkt ab sowie von der Funktion und der Qualifikation des Arbeitnehmers (zit. Urteil 8C_151/2010 E. 2.7 in fine mit Hinweisen). Der Streitwert ist nicht schematisch danach zu bemessen, ob das Zeugnis ganz oder teilweise umstritten ist. Massgebend ist vielmehr, ob es beim Streit um wesentliche Punkte des Zeugnisses geht (vgl. Urteil des Bundesgerichts 8C_220/2011 vom 2. März 2012 E. 1.2). Wenn der Beschwerdeführer geltend macht, die Zeugnisausstellung an sich sei Streitgegenstand gewesen und nicht nur die Formulierung eines einzelnen Absatzes, und einfach einen Streitwert von einem Monatslohn behauptet, genügt er den Begründungsanforderungen (<ref-law>) nicht. Er müsste vielmehr aufgrund seiner konkreten Situation im Einzelnen aufzeigen, weshalb der Streitwert bei willkürfreier Würdigung der tatsächlichen Gegebenheiten auf einen Monatslohn festzusetzen ist und inwiefern der von der Vorinstanz angenommene Wert offensichtlich nicht der Bedeutung entspricht, die dem Arbeitszeugnis objektiv zukommt. Mangels hinreichender Begründung ist insoweit nicht auf die Beschwerde einzutreten.
5.
Der Beschwerdeführer beanstandet sodann die Festsetzung der vollen Parteientschädigung nach dem Streitwert gemäss der HonO/SG. Die Vorinstanz begründe nicht, weshalb sie statt dem geforderten maximalen Zuschlag gemäss Art. 17 HonO/SG von 25 % nur einen solchen von 15 % gewähre. Es gebe keinen Grund, vom geforderten Zuschlag abzuweichen. Dieser erweise sich im Gegenteil mit Blick auf den erforderlichen Zeitaufwand und die Schwierigkeit des Falles als gerechtfertigt. Der Beschwerdeführer verweist diesbezüglich namentlich auf die Komplexität des Verfahrens zufolge des internationalen Aspekts und die Frage der Sistierung/Einstellung des Verfahrens gemäss <ref-law>. Auch mit Bezug auf die zweitinstanzliche Parteientschädigung ist er der Auffassung, da die Vorinstanz nicht begründe, weshalb sie von seinen Anträgen abweiche, sei auf diese abzustellen.
5.1. Die Anwendung des kantonalen Tarifs betreffend die Kosten- und Entschädigungsfolgen kann das Bundesgericht in der Beschwerde in Zivilsachen nicht prüfen (<ref-law>). Gerügt werden kann lediglich, die Anwendung führe zu einer Verletzung von Bundesrecht, namentlich des Willkürverbots in <ref-law> (<ref-ruling> E. 2.4 S. 249; <ref-ruling> E. 1.2 S. 382 f.). Für eine derartige Rüge sind erhöhte Begründungsanforderungen einzuhalten (<ref-law>; <ref-ruling> E. 6 S. 397 mit Hinweis). Eine Verletzung seines Anspruchs auf rechtliches Gehör (<ref-law>) zufolge mangelnder Begründung des angefochtenen Entscheides rügt der Beschwerdeführer nicht, so dass diese Frage nicht zu prüfen ist (<ref-law>). Zu prüfen bleibt, ob die Vorinstanz die kantonalrechtlichen Tarife willkürlich angewendet hat. W illkürlich ist ein Entscheid indessen nach konstanter Rechtsprechung nicht schon dann, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre. Das Bundesgericht hebt einen kantonalen Entscheid wegen Willkür vielmehr nur auf, wenn er offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Dabei genügt es nicht, wenn sich nur die Begründung des angefochtenen Entscheides als unhaltbar erweist. Eine Aufhebung rechtfertigt sich nur dann, wenn der Entscheid auch im Ergebnis verfassungswidrig ist (<ref-ruling> E. 2.2.2 S. 318 f. mit Hinweisen).
5.2. Dass die Vorinstanz nicht im Einzelnen begründet, weshalb sie den Anträgen des Beschwerdeführers nicht gefolgt ist, genügt nicht, um den angefochtenen Entscheid als im Ergebnis willkürlich auszuweisen. Auch dass der Beschwerdeführer angibt, wie die Berechnung seiner Ansicht nach korrekt hätte erfolgen müssen, reicht dazu nicht aus. Er müsste vielmehr aufzeigen, dass die Berechnung der Vorinstanz im konkreten Fall zu offensichtlich unhaltbaren Ergebnissen führt. Diesen Anforderungen genügt die Beschwerdeschrift nicht, da der Beschwerdeführer nicht darlegt, welcher Aufwand konkret notwendig war, der mit der von der Vorinstanz angenommenen Entschädigung offensichtlich nicht hinreichend abgegolten wäre. Entsprechende Ausführungen in der Replik wären verspätet (<ref-law>), da dazu bereits der angefochtene Entscheid Anlass gegeben hätte.
6.
Der Beschwerdeführer weist schliesslich darauf hin, dass die Vorinstanz die Überstunden nach <ref-law> geschätzt hat. Es hätte berücksichtigt werden müssen, dass er bezüglich der Überstunden im Grundsatz obsiegt habe. Zudem habe es die Beschwerdegegnerin zu verantworten, dass eine genaue Berechnung der Überstunden nicht möglich gewesen sei, da sie entgegen ihren gesetzlichen Pflichten die Kontrollrapporte des Sicherheitsdienstes, aus denen sich die Präsenzzeiten der Arbeitnehmer ergeben hätten, nicht aufbewahrt beziehungsweise (nach Überzeugung des Beschwerdeführers) deren Herausgabe im Prozess trotz Besitz der Unterlagen einfach verweigert habe. Dadurch habe die Beschwerdegegnerin unnötigen Aufwand verursacht.
6.1. Grundsätzlich werden die Prozesskosten der unterliegenden Partei auferlegt (<ref-law>) beziehungsweise nach dem Ausgang des Verfahrens verteilt, wenn keine Partei vollständig obsiegt (<ref-law>). Nach <ref-law> kann das Gericht von den Verteilungsgrundsätzen gemäss <ref-law> abweichen und die Prozesskosten nach Ermessen verteilen, um besonderen Umständen Rechnung zu tragen, beispielsweise wenn die Klage zwar grundsätzlich, aber nicht in der Höhe der Forderung gutgeheissen wurde und diese Höhe vom gerichtlichen Ermessen abhängig oder die Bezifferung des Anspruchs schwierig war (<ref-law>). Das Gesetz räumt dem Gericht damit den Spielraum ein, auf Billigkeitserwägungen zurückzugreifen, wenn im Einzelfall die Belastung der unterlegenen Partei mit Prozesskosten als ungerecht erscheint (<ref-ruling> E. 4.2 S. 35 mit Hinweis). Räumt das Gesetz dem kantonalen Gericht derartige Ermessensspielräume zur Berücksichtigung des Einzelfalles ein, übt das Bundesgericht bei der Überprüfung solcher Entscheide Zurückhaltung und schreitet nur ein, wenn die Vorinstanz grundlos von in Lehre und Rechtsprechung anerkannten Grundsätzen abgegangen ist, wenn sie Umstände berücksichtigt hat, die für den Entscheid im Einzelfall keine Rolle hätten spielen dürfen oder umgekehrt solche ausser Betracht gelassen hat, die hätten beachtet werden müssen. Es greift ausserdem in Ermessensentscheide ein, wenn sich diese als offensichtlich unbillig, als in stossender Weise ungerecht erweisen (vgl. <ref-ruling> E. 2 S. 123 f. mit Hinweisen).
6.2. Bezüglich der Überstunden hat der Beschwerdeführer zwar im Grundsatz obsiegt. Die Vorinstanz hat indessen die Anzahl der Überstunden entsprechend der vom Beschwerdeführer selbst vor Durchführung des Beweisverfahrens vorgenommenen Schätzung festgelegt. Die Erhöhung der Forderung im kantonalen Verfahren basiert auf den Aussagen eines Zeugen, dessen Präsenzzeiten nach den Feststellungen der Vorinstanz geringer waren als diejenigen des Beschwerdeführers und der daher über das Ausmass der Überstunden keine genauen Angaben machen konnte. Der Beschwerdeführer durfte mithin nicht davon ausgehen, der Zeuge wisse über die Anzahl der Überstunden besser Bescheid als er selbst. Die Zeugenaussage bildete keinen hinreichenden Grund für eine Erhöhung der Forderung des Beschwerdeführers. Da die Vorinstanz auf die ursprüngliche Schätzung des Beschwerdeführers abstellte, hat sie das ihr zustehende Ermessen nicht überschritten, wenn sie im Ergebnis von der Möglichkeit einer vom Prozesserfolg abweichenden Verteilung der Prozesskosten (<ref-law>) keinen Gebrauch machte.
6.3. Nicht schlüssig sind die Ausführungen, die Beschwerdegegnerin habe unnötigen Aufwand verursacht, indem sie Beweismittel nicht aufbewahrt habe. Nach <ref-law> hat unnötige Prozesskosten zwar zu bezahlen, wer sie verursacht hat. Die Abschätzung der Überstunden und der damit verbundene Aufwand waren aber notwendig, um dem Beschwerdeführer eine Überstundenentschädigung zusprechen zu können. Dass die Beschwerdegegnerin über die zur Bestimmung der Überstunden notwendigen Aufzeichnungen tatsächlich noch verfügt hätte, ist nicht festgestellt (<ref-law>).
7.
Soweit der Beschwerdeführer die Parteikostenverteilung für das zweitinstanzliche Verfahren mit Blick auf den von ihm angenommenen höheren Streitwert beanstandet, hat sich seine Rüge als unbegründet erwiesen (vgl. E. 4 hiervor). Er ist aber der Auffassung, indem er bloss 8/10 der Gesamtentschädigung erhalten habe, sei auch die Beschwerdegegnerin entschädigt worden, was mangels Antrags unzulässig sei. Die Beschwerdegegnerin hatte indessen in Ziff. 2 ihrer Rechtsbegehren vor der Vorinstanz beantragt: " Die Kosten gehen zu Lasten des Berufungsbeklagten ". Nach <ref-law> umfassen die Prozesskosten sowohl die Gerichtskosten (Abs. 1) als auch die Parteientschädigung (Abs. 2). Da ein Antrag für die Gerichtskosten, die von Amtes wegen festgesetzt und verteilt werden (<ref-law>), nicht nötig wäre, ist nach dem Vertrauensprinzip davon auszugehen, dass der Antrag bezüglich der Kostentragung auch die Parteientschädigung einschloss (vgl. SCHMID, in: ZPO: Schweizerische Zivilprozessordnung, Oberhammer [Hrsg.], a.a.O., N. 3 zu <ref-law>).
8.
Die Beschwerde ist insgesamt abzuweisen, soweit angesichts der mangelhaften Begründung überhaupt darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Kantonsgericht St. Gallen, III. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 6. Juni 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Luczak