Faits: A. Le 22 janvier 2012, la police a interpellé Y._ qui circulait en état d'ébriété, avec une alcoolémie de 1.74 o/oo, au volant de son véhicule à la Rampe du Pont-Rouge à Genève. Durant ce contrôle, un agent a fait le lien entre la voiture de Y._ et un véhicule ayant pris la fuite à la suite d'un accident survenu à la rue Vautier, les plaques d'immatriculation correspondant à celles transmises par les témoins de l'accident. Y._ a nié être l'auteur de cet accident, précisant que son véhicule était endommagé "depuis longtemps". Le 24 avril 2012, le Ministère public a rendu une ordonnance pénale déclarant Y._ coupable de conduite en état d'ébriété avec un taux d'alcool qualifié, de violation simple des règles de la circulation routière, de violation des devoirs en cas d'accident et de conduite d'un véhicule sans être porteur des permis ou autorisations nécessaires. Le 7 mai 2012, Y._ a formé opposition. Le 6 juin 2012, le Ministère public a rendu une nouvelle ordonnance pénale déclarant Y._ coupable de conduite en état d'ébriété avec un taux d'alcool qualifié et de conduite d'un véhicule sans être porteur des permis ou autorisations nécessaires. L'ordonnance constate qu'il n'est pas établi que l'intéressé est l'auteur de l'accident survenu à la rue Vautier, de sorte qu'il n'est "pas entré en matière sur les infractions y relatives". Le 20 juin 2012, X._, détenteur du véhicule accidenté à la rue Vautier, a été informé par l'assurance de Y._ que celui-ci avait été libéré de la prévention de cet accident. Le 22 juin 2012, X._ a formé opposition à l'ordonnance pénale du 6 juin 2012 et s'est constitué partie plaignante au pénal et au civil. Par courrier du 7 août 2012, constatant que "la décision de non-entrée en matière implicite" résultant de l'ordonnance pénale du 6 juin 2012 n'avait pas été communiquée à X._, le Ministère public lui a formellement notifié une "ordonnance de non-entrée en matière partielle" s'agissant des infractions visées par les art. 90 ch. 1 et 92 ch. 1 LCR, et, compte tenu de cette "nouvelle" décision, lui demandait si l'opposition à cette ordonnance pénale était maintenue. B. X._ a formé un recours contre l'ordonnance du 7 août 2012 auprès de la Chambre pénale de recours de la Cour de justice de la République et canton de Genève. Par arrêt du 26 octobre 2012, ce recours a été déclaré irrecevable. En substance, la cour cantonale a considéré que la constitution de partie plaignante de X._ était tardive au regard de l'art. 118 al. 3 CPP, car elle avait été annoncée après la clôture de la procédure préliminaire, ce qui devait être sanctionné par une irrecevabilité. C. Agissant par la voie du recours en matière pénale, X._ demande au Tribunal fédéral d'annuler l'arrêt cantonal et de retourner le dossier à la Cour de justice pour nouvelle décision dans le sens des considérants. La cour cantonale se réfère aux considérants de son arrêt. Y._ conclut, sous suite de frais et dépens, au rejet du recours. Le Ministère public en fait de même. Le recourant a déposé des observations complémentaires. 