Faits : A. A.a. Le 24 juin 2015, la police genevoise a adressé au Ministère public de la République et canton de Genève un rapport l'informant qu'un Ghanéen inconnu se livrait à un important trafic de cocaïne à Genève et recevait régulièrement des livraisons d'Espagne, la dernière étant intervenue les 20 et 21 juin 2015; ces renseignements avaient été obtenus par des "sources confidentielles et sûres". Dans un second rapport daté du même jour, la police suggérait la surveillance - active et rétroactive - du raccordement utilisé par le Ghanéen ("07***9"). Ces mesures ont été immédiatement ordonnées par le Procureur, puis autorisées le lendemain par le Tribunal des mesures de contrainte (Tmc). La mesure de surveillance a mis en évidence qu'entre le 19 et le 21 juin 2015, il y avait eu 28 échanges entre le raccordement susmentionné et le numéro "07***6", ce dernier étant probablement détenu par une "mule" (cf. le rapport de police du 12 juillet 2015); la police a requis une surveillance rétroactive de ce second numéro, mesure ordonnée par le Ministère public et approuvée par le Tmc le 13 juillet 2015. La police a encore indiqué que la première connexion n'avait plus été utilisée, son détenteur ayant quitté la Suisse. Le 16 juillet 2015, la police a avisé le Procureur qu'elle suspectait l'utilisateur du numéro "07***9" d'être revenu en Suisse le jour précédent et qu'une livraison de cocaïne était imminente; le contrôle technique d'un troisième numéro semblant lié à ces événements ("0034***6") a été suggéré. Le Ministère public l'a ordonné immédiatement et le Tmc l'a approuvé ce même jour. Le Procureur a été informé le 18 juillet 2015 que le détenteur du numéro "07***9" utilisait un même boîtier avec plusieurs cartes SIM, afin de séparer ses appels courants de ceux liés au trafic présumé de stupéfiants. Une surveillance de l'appareil (IMEI) a été alors ordonnée par le magistrat, respectivement approuvée par le Tmc. A.b. Le 19 juillet 2015, A._, ressortissant ghanéen, a été appréhendé en compagnie d'une tierce personne. Cette dernière arrivait de Barcelone et transportait 1.3 kg de cocaïne; l'étiquette de son bagage portait en outre une étiquette aéroportuaire relative à un voyage entre Genève et Barcelone le 20 juin 2015. Quant à A._, il était en possession d'un appareil téléphonique raccordé au numéro "07***9"; il a admis avoir organisé l'acquisition de la drogue en Espagne et son transfert en Suisse, contestant en revanche toute autre importation. Il a été mis en prévention de trafic aggravé de stupéfiants et placé en détention. Lors de l'audience du 29 octobre 2015, A._ a été informé des mesures de surveillance secrète portant sur son raccordement téléphonique et sur son appareil entre le 24 juin et le 23 juillet 2015, respectivement entre le 18 et le 23 juillet 2015. B. Le 19 janvier 2016, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté le recours déposé par A._ contre les ordonnances rendues les 25 juin, 13 et 16 juillet 2015 par le Tmc, ainsi que contre celles du Ministère public des 24 juin, 13 et 16 juillet 2015. C. Par acte du 19 février 2016, A._ forme un recours en matière pénale contre cet arrêt, concluant à son annulation, ainsi qu'à celles des décisions relatives à la surveillance secrète - rétroactive et active - du Tmc, respectivement du Ministère public, mise en oeuvre à son encontre. Il demande en substance le constat de l'illicéité de ces mesures et le retrait de la procédure de tous les éléments, documents et supports d'information établis grâce à ces moyens. A titre subsidiaire, il requiert le renvoi de la cause à l'autorité précédente pour nouvelle décision. Le recourant sollicite également l'octroi de l'assistance judiciaire. L'autorité précédente a renoncé à déposer des déterminations. Quant au Ministère public, il a conclu au rejet du recours. Le 21 avril 2016, le recourant a persisté dans ses conclusions, relevant notamment l'avis de prochaine clôture rendu par le Procureur.