Faits: A. Le 31 août 2012, A._, ressortissant suisse et guatémaltèque, a été arrêté dans le cadre d'une enquête conduite par le Ministère public du canton de Genève (ci-après: le Ministère public). Il lui est reproché d'avoir exécuté ou fait exécuter douze personnes entre novembre 2005 et septembre 2006, alors qu'il était Directeur général de la Police nationale civile du Guatemala (PNC). L'instruction genevoise porte sur deux cas. Fin 2005, alors que 19 prisonniers s'étaient évadés de la prison de haute sécurité " El Infiernito ", A._ aurait, avec notamment des membres du Ministère de l'intérieur et de la PNC, ordonné l'exécution de cinq des évadés. En juin 2006, des dirigeants du Ministère de l'intérieur, de l'armée et de la police civile et pénitentiaire, dont le prénommé, auraient élaboré un plan visant à reprendre le contrôle de la prison Pavón, qui comptait environ 1'800 détenus et que son administration ne maîtrisait plus. Dans le cadre de cette opération, le 25 septembre 2006, sept détenus auraient été tués sous le commandement de la PNC et de l'Armée nationale. Le 6 octobre 2011, les autorités du Guatemala ont répondu à la commission rogatoire décernée le 18 avril 2011 par le Ministère public et lui ont transmis un rapport de la Commission internationale contre l'impunité au Guatemala (CICIG) sur les faits précités, accompagné de différents témoignages, rapports de police, autopsies, photographies et DVD ainsi que quatre mandats d'arrêts internationaux - émis par la justice guatémaltèque le 6 août 2010 - dont un à l'encontre de A._. B. La détention de A._ a été régulièrement prolongée. Le 12 mars 2013, le Tribunal fédéral avait rejeté le recours formé par le prénommé contre un arrêt de la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) confirmant son maintien en détention provisoire (cause 1B_60/2013). En mars et avril 2013, le Ministère public a procédé aux auditions de plusieurs témoins qui avaient participé à l'enquête de la CICIG ainsi qu'à celles de B._, directeur général des Services pénitentiaires et de C._, détenu en Autriche. Le 9 mars 2013, A._ a formé une nouvelle demande de mise en liberté, que le Tribunal des mesures de contrainte du canton de Genève (Tmc) a refusée, par décision du 19 mars 2013. Par arrêt du 26 avril 2013, la Cour de justice a rejeté le recours de A._ contre l'ordonnance du 19 mars 2013. Elle a considéré en substance que les charges étaient suffisantes et qu'il existait un risque de fuite et de collusion. C. Agissant par la voie du recours en matière pénale, A._ demande principalement au Tribunal fédéral d'annuler l'arrêt de l'instance précédente et "d'ordonner sa remise en liberté immédiate moyennant le dépôt de tous ses passeports". Il conclut subsidiairement à sa mise en liberté moyennant toutes autres mesures de substitution jugées utiles par le Tribunal de céans. Il requiert en outre l'assistance judiciaire. La Cour de justice se réfère aux considérants de son arrêt et n'a pas d'observations à formuler. Le Ministère public conclut au rejet du recours. Le recourant a répliqué.