Sachverhalt: A. A._ (Beschwerdeführer) ist von Beruf Rechtsanwalt. Er ist seit dem 19. September 2008 Inhaber der Schweizer Wortmarke "YOU", die am 14. Juli 1976 als Nr. 2P-xxxx ins Markenregister eingetragen wurde. Diese Marke wird für "Seifen, Parfümerien, ätherische Oele, Mittel zur Körper- und Schönheitspflege, Haarwässer, Zahnputzmittel" der Klasse 3 nach dem Abkommen von Nizza über die internationale Klassifikation von Waren und Dienstleistungen für die Eintragung von Marken, revidiert in Genf am 13. Mai 1977 (SR 232.112.9; nachfolgend "Nizza-Klassifikation") beansprucht. Zudem ist er Inhaber der am 26. Februar 2008 als Nr. yyyy eingetragenen Schweizer Wortmarke "YOU". Diese Marke wird für "Wasch- und Bleichmittel; Putz-, Polier-, Fettentfernungs- und Schleifmittel; Seifen; Parfümeriewaren, ätherische Öle, Mittel zur Körper- und Schönheitspflege, Haarwässer, Zahnputzmittel" der Klasse 3 sowie "medizinische und veterinärmedizinische Dienstleistungen; Gesundheits- und Schönheitspflege für Menschen und Tiere; Dienstleistungen im Bereich der Land-, Garten- und Forstwirtschaft" der Klasse 44 gemäss Nizza-Klassifikation beansprucht. Die Z._ Switzerland AG (Beschwerdegegnerin) ist eine in I._/ZH ansässige Aktiengesellschaft, die den Handel mit Waren aller Art bezweckt. Sie betreibt in der Schweiz die Parfümeriekette "Z._" mit über 100 Verkaufsstellen, gibt das "Z._ Magazin" heraus und führt eine Webseite unter der Internetadresse "www.z._.ch". Die Beschwerdegegnerin ist eine Tochtergesellschaft der in Paris ansässigen Z._ S.A., die in die Q._-Gruppe, eine Detailhandelsgruppe des internationalen Mischkonzerns R._ Ltd. mit Sitz in Hongkong, integriert ist. B. Der Beschwerdeführer reichte am 1. März 2010 beim Handelsgericht des Kantons Zürich eine Markenverletzungsklage gegen die Beschwerdegegnerin ein. Er machte geltend, diese verletze seine Markenrechte durch die drohende Wiederverwendung des Zeichens: und durch die Verwendung bzw. drohende Wiederverwendung der Zeichen und und . Mit Rechtsbegehren vom 24. Oktober 2011 verlangte er Folgendes: "1. Es sei die Beklagte unter Androhung der Bestrafung ihrer Organe wegen Ungehorsams gegen eine amtliche Verfügung im Sinne von Art. 292 StGB (Bestrafung mit Busse) im Widerhandlungsfalle zu verurteilen, die mit dem Zeichen und/oder und/oder versehenen Werbemittel zur Bewerbung von Make-up Paletten und die in ihren Geschäften befindlichen mit dem Zeichen und/oder und/oder versehenen Verpackungen für Make-up Paletten, innerhalb von 2 Tagen nach Rechtskraft des Urteils im vorliegenden Verfahren zu entfernen und ab diesem Zeitpunkt keine Kataloge mehr zu vertreiben, in welchen diese Make-up Paletten unter der Bezeichnung und/oder und/oder abgebildet sind. 2. Es sei der Beklagten unter Androhung der Bestrafung ihrer Organe wegen Ungehorsams gegen eine amtliche Verfügung im Sinne von Art. 292 StGB (Bestrafung mit Busse) im Widerhandlungsfalle zu verbieten, das Zeichen oder das Zeichen oder das Zeichen oder das Zeichen auf oder im Zusammenhang mit Schönheits- und Körperpflegeprodukten wie insbesondere Nagelpflege- und Nagelverschönerungsprodukten und Make-up Paletten zu verwenden, insbesondere zur Kennzeichnung entsprechender Produkte in ihren Verkaufsgeschäften, auf ihrer Webseite und in ihrem Katalog "Z._ Magazin". 3. Es sei die Beklagte zu verurteilen, Herkunft und Menge der in ihrem Besitze befindlichen Schönheits- und Körperpflegeprodukte wie insbesondere Nagelpflege- und Nagelverschönerungsprodukte und Make-up Paletten mit der Kennzeichnung und/oder und/oder und/oder zu nennen sowie Auskunft zu geben über die Adressaten und das Ausmass, insbesondere die Stückzahl und Frankenumsatz der verkauften Produkte sowie die Weitergabe an allfällige Abnehmer". Die Beschwerdegegnerin erhob Widerklage mit den Anträgen: "1. Es sei die Nichtigkeit der Schweizer Marke Nr. 2P-xxxx festzustellen. 2. Es sei die Nichtigkeit der Schweizer Marke Nr. yyyy festzustellen. 3. Die Feststellung der Nichtigkeit sei dem Eidgenössischen Institut für Geistiges Eigentum in Bern zwecks Löschung der Marken Nr. 2P-xxxx und Nr. yyyy im schweizerischen Markenregister zu melden." Mit Urteil vom 4. September 2012 wies das Handelsgericht die Klage ab. In Gutheissung der Widerklage stellte es fest, dass die Schweizer Marken Nrn. 2P-xxxx und yyyy nichtig sind. Das Handelsgericht prüfte zuerst die Widerklage auf Feststellung der Nichtigkeit der klägerischen Marken "YOU". Es erachtete das Wort "YOU" als freihaltebedürftig und liess offen, ob ihm auch die nötige Unterscheidungskraft fehle. Da es bereits wegen Freihaltebedürftigkeit die Nichtigkeit der klägerischen Marken feststellte, erübrigte es sich für das Handelsgericht, die weiter geltend gemachten Nichtigkeitsgründe, namentlich den angeblich fehlenden Gebrauch beider Marken und die angeblich rechtsmissbräuchliche Hinterlegung der Marke Nr. yyyy, zu prüfen. Auch ergab sich aus der Feststellung der Nichtigkeit der klägerischen Marken ohne weiteres die Abweisung der Hauptklage. C. Der Beschwerdeführer beantragt mit Beschwerde in Zivilsachen, das Urteil des Handelsgerichts vom 4. September 2012 aufzuheben, die Widerklage abzuweisen und die Klage gutzuheissen. Eventualiter sei die Klage zur Neubeurteilung an das Handelsgericht zurückzuweisen. Die Beschwerdegegnerin beantragt, auf die Beschwerde nicht einzutreten, eventualiter sie abzuweisen. Das Urteil des Handelsgerichts sei zu bestätigen. Die Vorinstanz verzichtete auf eine Vernehmlassung. Der Beschwerdeführer reichte eine Replik ein.