Sachverhalt: A. C._ (Arbeitnehmer, Kläger, Beschwerdeführer) arbeitete seit dem 1. Oktober 2002 bei der 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 3. September 2010 kündigte die Arbeitgeberin das Arbeitsverhältnis mit dem Arbeitnehmer auf den 30. November 2010, wobei sie ihm gleichzeitig einen neuen Arbeitsvertrag per 1. Dezember 2010 anbot, welchen er nicht annahm. Am 14. 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. 34'873.-- (ohne Sozialversicherungsabzüge) als Entschädigung wegen missbräuchlicher Kündigung sowie Fr. 7'740.-- brutto (Fr. 7'256.-- 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 gutgeheissen und die Beklagte verurteilt, dem Kläger CHF 42'613.00 nebst 5 % Zins seit 6. April 2011 zu bezahlen, wovon von CHF 7'740.00 die gesetzlichen und vertraglichen Sozialbeiträge abzu- ziehen sind. 2. Die Kosten des Schlichtungsverfahrens von CHF 300.00 werden der Beklagten auferlegt. Die Gerichtsgebühr beträgt CHF 4'400.00 und wird der Beklagten auferlegt. Die Beklagte hat dem Kläger eine Parteientschädigung von CHF 6'379.70 (inkl. Auslagen und MWST von CHF 472.55) 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 ersetzte ihn durch diesen Entscheid (Ziffer I des Entscheids) : "1. Die Klage wird teilweise gutgeheissen und die Beklagte verurteilt, dem Kläger CHF 29'060.40 nebst 5 % Zins seit 6. April 2011 zu bezahlen. Von diesem Betrag sind keine gesetzlichen und vertraglichen Sozialbeiträge abzuziehen. Die Mehrforderung wird abgewiesen. 2. Die Kosten des Schlichtungsverfahrens von CHF 300.-- werden zu einem Fünftel dem Kläger und zu vier Fünfteln der Beklagten auferlegt. Die Gerichtsgebühr beträgt CHF 4'400.-- und wird zu einem Fünftel dem Kläger und zu vier Fünfteln der Beklagten auferlegt. Die Beklagte hat dem Kläger eine Parteientschädigung von CHF 3'827.80 (inkl. Auslagen und MWST) zu bezahlen." Die Gerichtsgebühr für das Berufungsverfahren von Fr. 4'000.-- auferlegte es zu vier Fünfteln bzw. Fr. 3'200.-- der Beklagten und zu einem Fünftel bzw. Fr. 800.-- 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 teilweise aufzuheben. In teilweiser Bestätigung des Urteils des Bezirksgerichts Arlesheim vom 31. Januar 2012, sei die Beklagte zu verurteilen, dem Kläger Fr. 36'800.40 nebst 5 % Zins seit 6. April 2011 zu bezahlen, wovon von Fr. 7'740.-- die gesetzlichen und vertraglichen Sozialbeiträge abzuziehen seien; die Kosten des Schlichtungsverfahrens von Fr. 300.-- sowie die Gerichtsgebühr von Fr. 4'400.-- seien vollumfänglich der Beklagten aufzuerlegen und diese sei zu verurteilen, ihm eine Parteientschädigung von Fr. 6'379.70 zu bezahlen. Sodann sei Ziffer II des Urteils des Kantonsgerichts Basel-Landschaft aufzuheben und die Gerichtskosten von Fr. 4'000.-- seien vollumfänglich der Beklagten aufzuerlegen und diese sei zu verpflichten, ihm 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.