Faits : A. Par ordonnance du 22 octobre 2015, le Tribunal d'application des peines et des mesures (TAPEM) a pris acte du retrait, par X._, de la requête formulée par ce dernier les 30 avril et 19 juin 2015, tendant au constat du caractère illicite de ses conditions de détention à la prison de Champ-Dollon du 22 septembre 2011 au 12 novembre 2012, puis du 29 mai au 1er juin 2013 (ch. 1). Dite requête a été déclarée irrecevable en tant qu'elle concernait l'examen des conditions de détention en exécution de peine dès le 2 juin 2013 (soit postérieurement à l'octroi du régime de l'exécution anticipée), faute de compétence du TAPEM pour prononcer un constat dans ce contexte (ch. 2). La requête, un rapport de la prison de Champ-Dollon du 15 mai 2015 ainsi que les observations du Ministère public du 26 mai 2015 ont été transmis au Département de la sécurité et de l'économie (DSÉ) afin qu'il examine les conditions de détention en exécution de peine, soit dès le 29 mai 2013, date du passage en régime d'exécution anticipée de la peine (ch. 3). B. X._ a recouru à la Chambre pénale de recours de la Cour de justice du canton de Genève contre cette décision, concluant à l'annulation du ch. 2 de l'ordonnance précitée, au renvoi de la cause au TAPEM afin que soit examinée la licéité de ses conditions de détention en exécution anticipée de la peine et à ce qu'il soit constaté que la décision querellée violait l'art. 13 CEDH en lien avec l'art. 3 CEDH en tant qu'elle le renvoyait à agir auprès du DSÉ. Par arrêt du 21 décembre 2015, la cour cantonale a rejeté le recours. C. X._ forme un recours en matière pénale au Tribunal fédéral. Il conclut, avec suite de frais et dépens, principalement, à la réforme de la décision entreprise en ce sens que sa requête soit déclarée recevable, à ce que soit constatée la violation de l'art. 13 CEDH en relation avec l'art. 3 CEDH en tant que la décision querellée le renvoie à agir devant le DSÉ et à ce que soit constatée la compétence du TAPEM pour juger de l'illicéité des conditions de détention pour la période du 2 juin au 3 septembre 2013. A titre subsidiaire, le recourant demande, en conséquence du constat de violation de l'art. 13 CEDH, que soit désignée une autorité administrative ou judiciaire, autre que le DSÉ, pour juger de l'illicéité des conditions de détention. Le recourant requiert, par ailleurs, le bénéfice de l'assistance judiciaire.