Faits:
A. Depuis 1981, X._ (ci-après: l'employé) a occupé différentes fonctions au sein d'un groupe devenu Y._ SA (ci-après: l'employeuse).
Au mois de décembre 2004, l'employeuse a soumis à ses travailleurs un formulaire disposant qu'"en vue d'avoir à fin 2004, et pour toutes les années de services, une situation parfaitement claire et précise des soldes de droit aux vacances de l'intégralité de nos employés et de leurs heures supplémentaires non compensées (sous quelque forme que ce soit), nous vous remercions de bien vouloir remplir le présent formulaire et le signer". L'employé a complété ce document en mentionnant un solde de 1494,5 heures supplémentaires; en procédure, il a précisé qu'il s'agissait de celles effectuées durant les années 2001 à 2004. Le formulaire comporte le visa de la société et la signature du directeur administratif et financier d'alors.
Dans le cadre d'un licenciement collectif, l'employé a reçu son congé le 9 avril 2006 pour le 31 octobre 2006, échéance finalement reportée au 31 décembre 2006 pour lui permettre de terminer certaines tâches liées à la restructuration du groupe.
Fin décembre 2006, l'employé a abordé le directeur général d'alors au sujet des heures supplémentaires en suspens. Par courrier du 15 janvier 2007, il a sollicité la liquidation du contentieux lié auxdites heures; il s'est prévalu d'un solde de 1494,5 heures en sa faveur à fin 2004 et a relevé que leur détail n'était plus disponible puisque toutes les feuilles de timbrage avaient certainement été détruites en 2005 lors de la réorganisation des archives. L'employeuse s'est opposée aux prétentions de l'employé.
B. Le 15 octobre 2007, l'employé a ouvert action contre l'employeuse, concluant au paiement de 113'024 fr. 05 avec intérêts à 5 % l'an dès le 1er janvier 2005; au débat final, l'employeuse a invoqué l'exception de prescription.
Par jugement du 31 mai 2010, la Cour civile II du Tribunal cantonal valaisan a condamné l'employeuse à payer à l'employé 17'077 fr. 60 avec intérêts à 5 % l'an dès le 1er janvier 2007. En substance, elle a considéré que le contenu du formulaire du 31 décembre 2004 avait été visé par le directeur administratif et financier d'alors et n'était pas infirmé par le dossier ni contesté par l'employeuse, de sorte que l'employé avait établi avoir effectué 1494,5 heures supplémentaires entre 2001 et 2004; cela étant, les prétentions dues pour l'indemnisation des heures supplémentaires faites avant le 15 octobre 2002 étaient prescrites; en procédure, le recourant avait expliqué avoir accompli les 1494,5 heures supplémentaires entre 2001 et le 31 décembre 2004, sans plus amples précisions; il n'avait pas versé en cause les fiches de timbrage afférentes à cette période en sorte qu'il n'était pas possible de connaître leur répartition et, partant, de déterminer le nombre d'heures atteintes par la prescription; même s'il ressortait du courrier du 15 janvier 2007 qu'il ne semblait plus être en possession desdites fiches, il aurait pu en requérir l'édition par l'intimée; dans ces circonstances, il n'y avait pas lieu de procéder, en application de l'art. 42 al. 2 CO, à une appréciation en équité et d'estimer le nombre d'heures non atteintes par la prescription; il s'ensuivait le rejet pur et simple de la totalité des prétentions réclamées en contrepartie des 1494,5 heures supplémentaires; en revanche, l'employé pouvait prétendre au montant de celles effectuées en 2005.
C. L'employé (le recourant) forme un recours en matière civile au Tribunal fédéral; se prévalant d'une violation des art. 42 al. 2 CO et 9 Cst., il conclut à l'annulation du jugement du 31 mai 2010 et à la transmission du dossier à la cour cantonale pour qu'elle statue sur la base des considérants du Tribunal fédéral. L'employeuse (l'intimée) propose le rejet du recours dans la mesure où il est recevable.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1.1, 329 consid. 1).
Selon l'art. 42 al. 1 LTF, les mémoires doivent indiquer les conclusions des parties. Saisi d'un recours en matière civile, le Tribunal fédéral peut en principe statuer lui-même sur le fond (art. 107 al. 2 LTF). Le recourant ne peut dès lors pas se borner à demander l'annulation de la décision attaquée, mais doit, en principe, sous peine d'irrecevabilité, prendre des conclusions sur le fond du litige. Les conclusions portant sur une somme d'argent doivent être chiffrées; des conclusions non chiffrées ne suffisent que si la somme déterminante soit d'emblée reconnaissable au regard de la motivation du recours ou de la décision entreprise. Il n'est fait exception à l'obligation de prendre des conclusions sur le fond que lorsque le Tribunal fédéral, en cas d'admission du recours, ne serait pas en situation de statuer lui-même à ce sujet et ne pourrait que renvoyer la cause à l'autorité cantonale (cf. <ref-ruling> consid. 2 p. 237, 379 consid. 1.3 p 383; <ref-ruling> consid. 3.1 p. 489 s.).
En l'espèce, le recourant se limite à conclure à l'annulation du jugement querellé et à la transmission du dossier à la cour cantonale pour nouvelle décision, à l'exclusion de toute conclusion sur le fond. Or, si l'on peut imaginer sur la base du dossier qu'il entend obtenir le paiement d'une indemnité pour les heures supplémentaires effectuées entre 2001 et 2004, l'on ignore le montant exact de sa prétention compte tenu de la prescription. En outre, l'on ne voit pas en quoi le Tribunal fédéral, s'il devait admettre le recours, ne serait pas en mesure de trancher lui-même sur le fond, ce que le recourant ne démontre - ni même n'invoque - pas davantage. La recevabilité du recours apparaît ainsi douteuse, question qui peut toutefois demeurer indécise, le recours étant de toute façon voué à l'échec, comme on le verra ci-après.
2. En premier lieu, le recourant reproche aux juges cantonaux d'avoir violé l'art. 42 al. 2 CO.
2.1 Selon l'art. 42 al. 1 CO, la preuve du dommage incombe au demandeur. A teneur de l'art. 42 al. 2 CO, lorsque le montant exact du dommage ne peut pas être établi, le juge le détermine équitablement en considération du cours ordinaire des choses et des mesures prises par la partie lésée. Cette dernière disposition, applicable par analogie lorsqu'il s'agit de déterminer l'ampleur des heures supplémentaires d'un travailleur (cf. <ref-ruling> consid. 2b/aa; cf. également arrêt 4A_95/2007 du 21 juin 2007 consid. 3.3), édicte une règle de preuve de droit fédéral dont le but est de faciliter au lésé l'établissement du dommage. Elle s'applique aussi bien à la preuve de son existence qu'à celle de son étendue. L'art. 42 al. 2 CO allège le fardeau de la preuve, mais il ne dispense cependant pas le lésé de toute preuve; au contraire, celui-ci doit alléguer et établir tous les éléments de faits constituant des indices de l'existence du dommage et de l'évaluation de son montant, dans la mesure où cela est possible et où on peut l'attendre de lui. L'exception de l'art. 42 al. 2 CO à la règle du fardeau de la preuve doit être appliquée de manière restrictive. Savoir si c'est à bon droit que le juge a - ou non - fait usage de la règle de l'art. 42 al. 2 CO est une question de droit fédéral, de même que le point de savoir si les faits allégués, en la forme prescrite et en temps utile, permettent de statuer sur la prétention déduite en justice; par contre, la détermination équitable de l'existence et du montant du dommage sont des questions de fait; le pouvoir d'estimation élargi découlant de cette disposition n'est pas un pouvoir d'appréciation juridique au sens de l'art. 4 CC (cf. <ref-ruling> consid. 4.2.2. p. 471; <ref-ruling> consid. 5.1 p. 363 s.; <ref-ruling> consid. 3a p. 221).
2.2 En l'occurrence, la cour cantonale a retenu que le recourant avait précisé en procédure que les 1495,5 heures supplémentaires avaient été effectuées durant les années 2001 à 2004; il n'a en revanche pas allégué quelle était la répartition de ces heures au cours de chacune de ces années. Il a en outre été retenu que le recourant n'avait pas versé en cause les fiches de timbrage relatives à cette période, ni requis leur édition par l'intimée.
A cet égard, le recourant se fonde vainement sur sa lettre du 15 janvier 2007 pour affirmer que ces pièces avaient été détruites; en effet, il ne faisait dans cet écrit qu'une supposition, ainsi qu'en atteste l'emploi du terme "certainement", qui ne permet pas d'établir la destruction effective et, partant, l'impossibilité matérielle de produire lesdites fiches; quoi qu'il en soit, cela ne le dispensait pas d'en solliciter à toutes fins utiles l'édition par son adverse partie, qui a d'ailleurs indiqué dans sa réponse au recours que "si (elle) avait été requise de produire les fiches en question, elle aurait été en mesure de le faire, ne serait-ce que sur la base d'un examen des fichiers informatiques si par hypothèse les documents papier avaient disparu, ce qui est contesté".
L'argument du recourant selon lequel il n'avait aucune raison d'en demander l'édition dès lors que le formulaire du 31 décembre 2004, visé par un des responsables d'alors de l'intimée, établissait clairement ses prétentions n'est pas davantage pertinent; en effet, les questions de savoir d'une part si un employé a effectué des heures supplémentaires, d'autre part s'il a droit - ou non - à une indemnité de ce chef, compte tenu en particulier de la prescription, sont différentes; si le document en cause permettait ainsi certes de déterminer le nombre d'heures supplémentaires effectuées, ce que la cour cantonale a d'ailleurs retenu, il ne suffisait pas pour autant pour établir l'étendue de la créance du recourant, respectivement le montant de l'indemnité due, compte tenu de la partie prescrite.
Enfin, le fait que l'intimée n'ait invoqué la prescription qu'à la fin de la procédure ne change quoi que plaide le recourant rien à la carence de celui-ci dans l'allégation et la réquisition d'édition de pièces, étant encore précisé que celui-ci ne prétend pas que la procédure aurait dû être régie par la maxime d'office.
Il apparaît ainsi que le recourant n'a pas fait tout ce qui était en son pouvoir pour permettre la détermination exacte du montant de sa créance, en ce sens qu'il n'a ni allégué la répartition des heures supplémentaires effectuées au cours de chacune des années 2001 à 2004, ni requis les moyens de preuve adéquats, faillissant ainsi à son obligation de preuve, sans démontrer qu'il aurait été dans l'impossibilité d'apporter la preuve de sa prétention, la destruction des fiches de timbrage n'étant pas établie; dans ces circonstances, la cour cantonale n'a pas violé le droit fédéral en refusant de faire usage de l'art. 42 al. 2 CO. Dès lors que les conditions d'application de cette disposition n'étaient pas remplies, il importait peu qu'il eût été, comme le recourant le soutient, "facile de procéder à une simple règle de trois entre les jours atteints par la prescription et ceux qui ne l'étaient pas (...) par une appréciation en équité", cette question n'entrant pas en ligne de compte dans la mesure où la disposition susmentionnée ne s'appliquait pas.
3. Le recourant soutient encore que le fait pour les juges cantonaux d'avoir refusé de procéder à une appréciation en équité des heures supplémentaires non prescrites relèverait de l'arbitraire, et aboutirait à un résultat choquant. A supposer encore que l'on puisse réellement lui reconnaître une portée autonome, cette argumentation tombe à faux, dans la mesure où il a été retenu que l'une des conditions d'application de l'art. 42 al. 2 CO faisait défaut.
4. Il résulte des considérants qui précèdent que le recours doit être rejeté dans la mesure de sa recevabilité, par un arrêt sommairement motivé (cf. art. 109 al. 2 et 3 LTF).
5. Comme la valeur litigieuse, calculée selon les prétentions à l'ouverture de l'action (<ref-ruling> consid. 5b p. 41), dépasse le seuil de 30'000 fr., le montant de l'émolument judiciaire est fixé selon le tarif ordinaire (art. 65 al. 3 let. b LTF) et non réduit (art. 65 al. 4 let. c LTF). Compte tenu de l'issue du litige, les frais judiciaires et dépens de l'intimée - fixés en considération de la brièveté de sa réponse (art. 8 al. 2 du règlement du 31 mars 2006 sur les dépens alloués à la partie adverse et sur l'indemnité pour la représentation d'office dans les causes portées devant le Tribunal fédéral [RS 173.110.210.3]) - sont mis à la charge du recourant, qui succombe (art. 66 al. 1 ainsi qu'art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 4'000 fr., sont mis à la charge du recourant.
3. Une indemnité de 2'500 fr., à payer à l'intimée à titre de dépens, est mise à la charge du recourant.
4. Le présent arrêt est communiqué aux mandataires des parties et à la Cour civile II du Tribunal cantonal valaisan.
Lausanne, le 11 août 2010
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Klett Cornaz