Sachverhalt: A. A._ (Arbeitnehmer, Kläger, Beschwerdeführer) arbeitete seit dem 21. April 1980 bei der X._ AG (Arbeitgeberin, Beklagte, Beschwerdegegnerin). Mit Schreiben vom 26. Juli 2010 teilte die Arbeitgeberin den in ihrem Betrieb angestellten Grenzgängern - wozu auch der Arbeitnehmer gehörte - mit, dass der schwache Eurokurs für die Grenzgänger eine Lohnerhöhung von mindestens 12 % zur Folge habe. Deshalb wurde ihnen vorgeschlagen, dass ihr Lohn ab dem 1. September 2010 um 6 % reduziert werde, wobei diese Massnahme bei einem Eurokurs von Fr. 1.50 wieder aufgehoben werde. Die Grenzgänger wurden aufgefordert, der Arbeitgeberin bis spätestens am 31. August 2010 ihre Zustimmung oder Ablehnung zur Lohnreduktion mitzuteilen. Der Arbeitnehmer lehnte die Reduktion ab. Mit Schreiben vom 6. September 2010 kündigte die Arbeitgeberin das Arbeitsverhältnis mit dem Arbeitnehmer auf den 31. Dezember 2010, wobei sie ihm gleichzeitig einen neuen Arbeitsvertrag per 1. Januar 2011 anbot, welchen er nicht annahm. Am 23. Oktober 2010 erhob der Arbeitnehmer bei der Arbeitgeberin Einsprache gegen die Kündigung und behielt sich eine Klage wegen missbräuchlicher Kündigung vor. B. B.a. Mit Klagebegründung vom 18. August 2011 beantragte der Arbeitnehmer dem Bezirksgericht Arlesheim, die Arbeitgeberin sei zu verurteilen, ihm Fr. 38'025.-- (ohne Sozialversicherungsabzüge) als Entschädigung wegen missbräuchlicher Kündigung sowie Fr. 24'613.-- brutto (Fr. 23'075.-- netto) als Entschädigung für geleistete Überstunden, je zuzüglich 5 % Zins ab Klageeinreichung zu bezahlen. Mit Entscheid vom 31. Januar 2012 erkannte das Bezirksgericht Arlesheim: "1. Die Klage wird teilweise gutgeheissen und die Beklagte verurteilt, dem Kläger CHF 46'465.00 nebst 5 % Zins seit 6. April 2011 zu bezahlen, wo- von von CHF 8'440.00 die gesetzlichen und vertraglichen Sozialbeiträge abzuziehen sind. 2. Die Kosten des Schlichtungsverfahrens von CHF 300.-- werden zu einem Viertel dem Kläger und zu drei Vierteln der Beklagten auferlegt. Die Ge- richtsgebühr beträgt CHF 5'000.00 und wird zu einem Viertel dem Kläger und zu drei Vierteln der Beklagten auferlegt. Die Beklagte hat dem Kläger eine reduzierte Parteientschädigung von CHF 3'325.30 (inkl. Auslagen und MWST von CHF 246.40) zu bezahlen." B.b. Gegen diesen Entscheid erklärte die Beklagte Berufung an das Kantonsgericht Basel-Landschaft mit dem Antrag, der Entscheid des Bezirksgerichts Arlesheim vom 31. Januar 2012 sei aufzuheben und die Klage abzuweisen. Mit Entscheid vom 17. Dezember 2012 hob das Kantonsgericht Basel-Landschaft in teilweiser Gutheissung der Berufung den Entscheid des Bezirksgerichts Arlesheim vom 31. Januar 2012 auf und ersetze ihn durch diesen Entscheid (Ziffer I des Entscheids) : "1. Die Klage wird teilweise gutgeheissen und die Beklagte verurteilt, dem Kläger CHF 38'025.-- nebst 5 % Zins seit 6. April 2011 zu bezahlen. Von diesem Betrag sind keine gesetzlichen und vertraglichen Sozial- beiträge abzuziehen. Die Mehrforderung wird abgewiesen. 2. Die Kosten des Schlichtungsverfahrens von CHF 300.-- werden zu zwei Fünfteln dem Kläger und zu drei Fünfteln der Beklagten aufer- legt. Die Gerichtsgebühr beträgt CHF 5'000.-- und wird zu zwei Fünf- teln dem Kläger und zu drei Fünfteln der Beklagten auferlegt. Die Beklagte hat dem Kläger eine Parteientschädigung von CHF 1'593.45 (inkl. Auslagen und MWST) zu bezahlen." Die Gerichtsgebühr für das Berufungsverfahren von Fr. 5'000.-- auferlegte es zu vier Fünfteln bzw. Fr. 4'000.-- der Beklagten und zu einem Fünftel bzw. Fr. 1'000.-- dem Kläger. Sodann verpflichtete es die Beklagte dem Kläger für das Berufungsverfahren eine Parteientschädigung von Fr. 2'103.-- zu bezahlen (Ziffer II des Entscheids). C. Mit Beschwerde in Zivilsachen und subsidiärer Verfassungsbeschwerde beantragt der Kläger dem Bundesgericht, Ziffer I des Entscheids des Kantonsgerichts Basel-Landschaft vom 17. Dezember 2012 sei aufzuheben, die Berufung der Beklagten vollumfänglich abzuweisen und den Entscheid des Bezirksgerichts Arlesheim vom 31. Januar 2012 zu bestätigen. Sodann sei Ziffer II aufzuheben und die Gerichtskosten von Fr. 5'000.-- seien vollumfänglich der Beklagten aufzuerlegen. Diese sei ausserdem zu verurteilen, dem Kläger eine Parteientschädigung von Fr. 3'505.-- zu bezahlen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei, eventuell die Rückweisung an die Vorinstanz zu neuer Entscheidung. Die Vorinstanz beantragt die Abweisung der Beschwerde.