Faits :
A.
Le 14 décembre 2015, le Tribunal correctionnel de la République et canton de Genève a condamné X._, né le 11 juillet 1993, à une peine privative de liberté de 18 mois sous déduction de 327 jours de détention avant jugement et à une amende de 300 fr. pour agression (<ref-law>), vol (<ref-law>), tentative de vol (art. 22 et 139 CP), dommages à la propriété (<ref-law>), violation de domicile (<ref-law>) et consommation de stupéfiants (<ref-law>). Le Tribunal a également ordonné la révocation des sursis octroyés les 30 novembre 2012 et 11 janvier 2014 par le Ministère public.
Le Tribunal a constaté que X._ avait été placé en exécution anticipée de peine à compter du 26 août 2015 et ordonné son placement dans un établissement pour jeunes adultes ainsi qu'un traitement psychothérapeutique ambulatoire (art. 61 et 63 CP), l'exécution de la peine étant suspendue au profit du placement dans l'établissement pour jeunes adultes.
B.
B.a. X._ a été incarcéré à la prison de Champ-Dollon du 18 octobre 2014 au 9 mars 2016, date à laquelle il a été transféré à l'établissement fermé de la Brenaz.
B.b. Le 22 décembre 2015, le Service d'application des peines et mesures (SAPEM) a adressé au Centre éducatif fermé de Pramont une demande d'admission concernant X._. Le centre précité a répondu le 4 janvier 2016 que l'établissement était complet, que X._ avait été placé sur liste d'attente, que le délai était relativement long et que l'admission pourrait ne pas avoir lieu en 2016.
B.c. Par courrier du 15 février 2016, X._, alors toujours détenu à la prison de Champ-Dollon, a sollicité son transfert sans délai dans un établissement pour jeunes adultes ou la libération conditionnelle. Il précisait qu'en tous les cas, il devait être libéré à la fin de sa peine privative de liberté de 18 mois. Le 22 février 2016, le SAPEM a indiqué à X._ qu'il se trouvait en exécution de mesure et non en exécution de peine, celle-ci ayant été suspendue au profit de la mesure au sens de l'<ref-law>, et ce bien que les délais d'attente pour obtenir une place au Centre éducatif fermé de Pramont soient très longs. Le même jour, X._ a saisi le TAPEM des faits qui précèdent, demandant notamment sa libération conditionnelle.
B.d. Les 2 et 3 mars 2016, X._ a demandé au SAPEM son transfert dans un établissement au sens de l'<ref-law> ou sa mise en liberté, après un constat formel de l'illicéité de sa détention, et a imparti au SAPEM un délai de 10 jours pour rendre une décision motivée. Le SAPEM lui a rappelé, par courrier du 7 mars suivant, avoir effectué une demande d'admission au Centre éducatif fermé de Pramont. Il a rejeté sa compétence pour se prononcer sur la mise en liberté, respectivement l'illicéité de la détention. Aucune décision n'était donc rendue en ce sens. X._ a formé recours contre ce courrier devant la Chambre pénale de recours de la Cour de justice.
B.e. Par arrêt du 29 juin 2016 (ACPR/396/2016), la Chambre pénale de recours de la Cour de justice a déclaré irrecevable le recours de X._ contre le courrier du SAPEM du 7 mars 2016, celui-ci ne contenant qu'une affirmation de réalités qui n'étaient pas de nature à modifier la situation juridique de l'intéressé.
C.
Par arrêt du même jour (ACPR/397/2016), la Chambre pénale de recours a partiellement admis le recours de X._ contre un jugement du TAPEM du 26 avril 2016 et renvoyé la cause au TAPEM pour instruction et nouvelle décision. Le TAPEM avait refusé la demande de libération conditionnelle, respectivement la levée de la mesure de traitement pour jeunes adultes (<ref-law>), ordonné la poursuite de cette mesure, ainsi que de celle de l'<ref-law> jusqu'au prochain contrôle annuel, et constaté que la demande de libération conditionnelle de la peine était irrecevable. En rapport avec ce jugement, la Chambre pénale de recours a retenu que le placement provisoire du précité en prison, dans l'attente de l'exécution de la mesure prononcée contre lui, était possible et licite. Cependant, dans la mesure où le centre de Pramont avait annoncé, en cours d'instruction du recours, qu'aucune place ne serait disponible avant de nombreux mois, la cause devait être retournée à l'autorité précédente pour instruction et nouvelle décision à l'aune de ce fait nouveau.
Le recours au Tribunal fédéral de X._ contre cet arrêt a été déclaré irrecevable (arrêt 6B_846/2016 du 12 septembre 2016).
D.
D.a. Le 30 juin 2016, date indicative de la fin de l'exécution de peine, X._ a été remis en liberté à la suite d'une erreur. Il a été interpellé par la police le 13 juillet 2016, immédiatement placé à Champ-Dollon, puis transféré, le lendemain, à la Brenaz.
D.b. X._ a formé un recours contre son interpellation du 13 juillet 2016 et sa réincarcération subséquente auprès de la Chambre pénale de recours.
D.c. Par arrêt du 11 novembre 2016, la Chambre pénale de recours a déclaré le recours irrecevable (ACPR/714/2016). En substance, elle a retenu que l'interpellation du 13 juillet 2016 était un acte matériel exécuté par l'autorité compétente, le SAPEM, et rendu nécessaire par une mise en liberté intervenue par erreur. La demande d'indemnisation pour détention illicite était également irrecevable, la Chambre pénale de recours ayant déjà retenu dans son arrêt du 29 juin 2016 que la détention était, en l'état, licite, et transmis le dossier au TAPEM pour le surplus.
E.
Le 10 novembre 2016, le TAPEM a ordonné la levée de la mesure de l'<ref-law>, celle-ci s'avérant durablement inexécutable (art. 62c al. 1 let. c CP), ainsi que la mise en liberté immédiate de l'intéressé, la mesure de l'<ref-law> devant en revanche être poursuivie.
F.
Contre l'arrêt du 29 juin 2016 rendu sur recours contre le courrier du SAPEM du 7 mars 2016 (ACPR/396/2016), X._ dépose un recours en matière pénale devant le Tribunal fédéral (6B_842/2016). Il conclut à la réforme de l'arrêt attaqué en ce sens qu'il soit constaté l'illicéité de la détention subie à la prison de Champ-Dollon et à l'établissement fermé de la Brenaz ainsi que la violation du principe de la célérité, et à ce qu'il soit dit qu'il ne peut être placé que dans un établissement pour jeunes adultes idoine pour l'exécution de la mesure de l'<ref-law> et, à défaut, à ce qu'il soit ordonné sa remise en liberté. Il sollicite en outre l'octroi d'une indemnité de 200 fr. par jour de détention illicite à la prison de Champ-Dollon et à l'Etablissement fermé de la Brenaz depuis le 24 décembre 2015 et jusqu'à son placement dans un établissement au sens de l'<ref-law> ou sa remise en liberté, avec intérêts de 5% dès le 24 décembre 2015.
X._ dépose également un recours en matière pénale au Tribunal fédéral contre l'arrêt du 11 novembre 2016 rendu sur recours contre l'interpellation du 13 juillet 2016 et la réincarcération subséquente (6B_1377/2016). Il conclut à sa réforme en ce sens qu'il soit constaté l'illicéité de la détention subie à la prison de Champ-Dollon et à l'établissement fermé de la Brenaz, à ce qu'il soit dit qu'il ne peut être placé que dans un établissement pour jeunes adultes pour l'exécution de la mesure de l'<ref-law>, à l'annulation et/ou la révocation des ordres d'interpellation et de placement à la prison de Champ-Dollon et à l'établissement fermé de la Brenaz exécutés les 13 et 14 juillet 2016, et à la constatation de la violation de la protection contre l'arbitraire et de la protection de la bonne foi. Il sollicite l'octroi d'une indemnité de 24'400 fr. en raison de sa détention illicite à la prison de Champ-Dollon et à l'établissement fermé de la Brenaz avec intérêts de 5% dès le 24 décembre 2015. A titre subsidiaire, il demande l'annulation de l'arrêt attaqué et le renvoi de la cause à l'autorité précédente pour nouveau jugement.
A l'appui de ses recours, X._ sollicite l'assistance judiciaire ainsi que la nomination de son conseil en qualité d'avocat d'office.
G.
Interpellés, la cour cantonale et le SAPEM ont renoncé à se déterminer.

Considérant en droit :
1.
Les deux recours en matière pénale adressés au Tribunal fédéral ont trait à un même complexe de faits et posent des questions connexes. Il y a donc lieu de joindre les causes et de les traiter dans un seul arrêt (<ref-law> et 71 LTF).
2.
Selon l'<ref-law>, a qualité pour former un recours en matière pénale quiconque a pris part à la procédure devant l'autorité précédente et a un intérêt juridique à l'annulation ou à la modification de la décision attaquée, à savoir, en particulier, l'accusé (art. 81 al. 1 let. a et b ch. 1 LTF).
2.1. Le recourant doit avoir un intérêt actuel et pratique au traitement de son recours (<ref-ruling> consid. 1.3; <ref-ruling> consid. 3). Selon la jurisprudence, lorsque la détention a pris fin, il n'y a en règle générale plus d'intérêt pratique et actuel à traiter un recours contre cette dernière (<ref-ruling> consid. 4a p. 397). Toutefois, dans des circonstances particulières, il se justifie d'examiner le recours au fond malgré la libération du recourant (<ref-ruling> consid. 1.3 p. 276). Il en va notamment ainsi lorsque le recourant invoque une violation de l'art. 5 CEDH (<ref-ruling> consid. 4.3.3 p. 302) et requiert une indemnité pour détention illicite (arrêt 6B_617/2015 du 27 août 2015 consid. 2.3).
2.2. Compte tenu du prononcé du TAPEM du 10 novembre 2016 ordonnant la levée de la mesure et la mise en liberté immédiate du recourant, ses conclusions tendant à sa mise en liberté ou son placement immédiat dans un établissement pour jeunes adultes, y compris par le biais de l'annulation et/ou la révocation des ordres d'interpellation et de placement en détention, n'ont plus d'objet. En revanche, dans la mesure où le recourant reproche à la cour cantonale d'avoir refusé d'entrer en matière sur le caractère illicite de sa détention et sa demande d'indemnisation, et qu'il allègue de manière suffisamment motivée une violation du principe de la célérité sous l'angle de l'art. 5 ch. 4 CEDH, il a un intérêt à l'annulation des arrêts attaqués en relation avec ces griefs.
L'objet du litige est, pour le surplus, circonscrit par les arrêts attaqués à l'irrecevabilité des recours cantonaux (<ref-law>; <ref-ruling> consid. 4.4.2 et réf. citée.), de sorte que le recourant n'est pas légitimé à faire valoir des griefs de fond (en l'espèce: violation de l'interdiction de l'arbitraire et du principe de la bonne foi).
3.
Le recourant se plaint des décisions d'irrecevabilité que la cour cantonale a opposées à ses recours à l'encontre de sa détention à la prison de Champ-Dollon puis à l'établissement fermé de la Brenaz dans l'attente d'un transfert dans un établissement pour jeunes adultes au sens de l'<ref-law>.
3.1.
3.1.1. L'art. 5 CEDH peut être invoqué par la personne soumise à un traitement institutionnel dans un établissement psychiatrique ou pénitentiaire fermé ou dans la section fermée d'un établissement pénitentiaire ouvert au sens de l'<ref-law> (cf. <ref-ruling> consid. 3.2 p. 161). Conformément à l'art. 5 par. 4 CEDH, la personne soumise à une telle mesure a donc droit d'introduire un recours devant un tribunal, afin qu'il statue à bref délai sur la légalité de sa détention et ordonne sa libération si la détention est illégale. Ces principes doivent également trouver application lorsque l'intéressé fait l'objet d'une mesure thérapeutique institutionnelle applicable aux jeunes adultes au sens de l'<ref-law> mais que, dans l'attente d'une place disponible dans un établissement idoine, il est détenu dans un établissement pénitentiaire fermé.
Selon l'art. 5 par. 1 let. e CEDH, toute personne a droit à la liberté et à la sûreté. Nul ne peut être privé de sa liberté, sauf selon les voies légales et s'il s'agit, notamment, de la détention régulière d'un aliéné. En principe, la « détention » d'une personne comme malade mental ne sera « régulière » au regard de l'article 5 par. 1 let. e CEDH que si elle se déroule dans un hôpital, une clinique ou un autre établissement approprié (v. parmi d'autres: arrêts CEDH Ashingdane c. Royaume-uni du 28 mai 1985 [requête no 8225/78] § 44; Aerts c. Belgique du 30 juillet 1998 [requête no 25357/94] § 46; Hutchison Reid c. Royaume-uni du 20 février 2003 [requête no 50272/99] § 49; L.B. c. Belgique du 2 octobre 2012 [requête no 22831/08] § 93; Papillo c. Suisse du 27 janvier 2015 [requête no 43368/08] § 42). L'Etat a l'obligation de mettre à disposition en nombre suffisant des places dans des établissements appropriés. Un séjour dans un établissement d'exécution des peines est envisageable pour autant qu'il soit nécessaire afin de trouver un établissement approprié. Il faut notamment examiner l'intensité des efforts fournis par l'autorité pour trouver un lieu d'accueil approprié. Si la détention s'étend sur une durée plus longue en raison de problèmes de capacité connus, elle est contraire à l'art. 5 CEDH. Dans ce sens, la CEDH a retenu que, dans un contexte où le manque structurel de place était connu depuis des années, un délai d'attente de six mois dans une prison était contraire à l'art. 5 CEDH. La détention dans une prison compromet les buts de la mesure - à savoir la resocialisation de l'intéressé par un traitement adéquat - et risque de renverser la priorité de la mesure sur la peine prévue par la loi. Il ne faut pas que le véritable but de la mesure ne réside plus que dans la mise en sûreté de l'intéressé. Une telle privation de liberté ne serait donc valable que sous des conditions très strictes (<ref-ruling> précité consid. 5.8.1 p. 115 s. et les références citées).
3.1.2. Le droit interne prévoit, conformément à l'<ref-law>, que les lieux d'exécution des mesures thérapeutiques visés aux art. 59 à 61 doivent être séparés des lieux d'exécution des peines. Selon l'<ref-law>, si l'auteur avait moins de 25 ans au moment de l'infraction et qu'il souffre de graves troubles du développement de la personnalité, le juge peut ordonner son placement dans un établissement pour jeunes adultes aux conditions suivantes: l'auteur a commis un crime ou un délit en relation avec ces troubles (let. a); il est à prévoir que cette mesure le détournera de nouvelles infractions en relation avec ces troubles (let. b). Selon l'<ref-law>, les établissements pour jeunes adultes doivent être séparés des autres établissements prévus par le CP.
Il incombe à l'autorité d'exécution de trouver une institution appropriée pour l'exécution de la mesure ordonnée par le juge. Aussi longtemps qu'aucune place disponible ne peut être trouvée, l'autorité d'exécution ne peut pas retenir un jeune adulte dans un établissement carcéral à titre de substitution et sans limite de temps. Ainsi, selon la jurisprudence rendue sous l'empire de l'ancien art. 100 bis CP, devenu l'<ref-law>, le fait qu'un établissement approprié ne puisse pas être trouvé ne justifie pas de placer la personne condamnée à une mesure institutionnelle dans un établissement pénitentiaire pendant des semaines ou des mois (<ref-ruling> consid. 5.8.1 p. 115 s. et les références citées). Le Tribunal fédéral a ainsi jugé qu'une détention de près de 3 mois ordonnée dans le but de " motiver " l'intéressé et de " préparer " la mesure ne reposait sur aucun fondement juridique (arrêt 1P.334/2003 du 17 juillet 2013 consid. 8.5-8.6). En revanche, la détention d'un condamné à une mesure dans un établissement carcéral était conforme au droit fédéral matériel dans le cas d'une situation d'urgence transitoire de courte durée (arrêt 6A.20/2006 du 12 mai 2006 consid. 4.5).
3.2.
3.2.1. Il ressort du dossier que, par décision du 29 juin 2016, la cour cantonale a confirmé l'absence de compétence du SAPEM pour statuer sur l'illicéité alléguée de la détention du recourant et elle a par ailleurs constaté l'inconsistance du grief en lien avec le principe de célérité (ACPR/396/2016). Par décision du même jour, elle a constaté la licéité de la détention aussi longtemps que sa durée n'était pas excessive, tout en renvoyant l'examen de l'éventuelle levée de la mesure au TAPEM (ACPR/397/2016; voir aussi: décision attaquée ACPR/714/2016 consid. 1.3). Le 11 novembre 2016, elle a refusé de se prononcer sur la licéité de la détention au motif que cette question avait déjà été tranchée dans l'arrêt ACPR/397/2016 du 29 juin 2016 et que le TAPEM avait été saisi pour le surplus (ACPR/714/2016). Celui-ci s'est toutefois déclaré incompétent, par jugement du 10 novembre 2016, pour statuer sur le caractère illicite et l'indemnisation de la détention du 13 juillet 2016 au 10 novembre 2016, renvoyant le recourant à agir par-devant le Département de la Sécurité et de l'économie (DSE). Il s'est de même déclaré incompétent pour constater une éventuelle violation du principe de célérité entre le 30 juin et le jour de son jugement. Le recourant a ainsi obtenu une décision sur le caractère licite de sa détention jusqu'au 29 juin 2016 (ACPR/397/2016), qu'il n'a toutefois pas pu soumettre au Tribunal fédéral s'agissant d'une décision incidente non sujette à recours. En effet, selon l'arrêt de la cour de céans (6B_846/2016), attendu que le sort de la demande de levée de la mesure était susceptible d'influer sur la durée de la détention à prendre en compte et sur l'indemnisation consécutive, la question du caractère illicite de la détention et de l'indemnisation ne pouvait pas être considérée comme indépendante de celle des points faisant l'objet du renvoi au TAPEM.
3.2.2. Ainsi, à teneur du dossier remis à la cour de céans, aucune autorité n'a statué sur la licéité de la détention du recourant en établissement carcéral en attente de son placement dans un établissement pour jeunes adultes en prenant en compte la durée totale de cette détention, à savoir plus de 10 mois. De même le recourant n'a-t-il, à la connaissance de la cour de céans, pas encore obtenu de décision sur le grief pris d'une violation du principe de célérité au regard de l'ensemble de la durée de détention. Il apparaît également que la compétence pour statuer sur ces griefs n'a pas encore été déterminée de manière définitive au niveau cantonal, la cour cantonale ayant renvoyé la cause au TAPEM et ce dernier s'étant déclaré incompétent pour statuer sur le caractère illicite de la détention ordonnée par le SAPEM à l'endroit d'une personne se trouvant en exécution de mesure à la suite d'un jugement entré en force. Quoi qu'il en soit, au regard de la durée de la détention du recourant en l'espèce, un constat d'illicéité de la détention peut d'emblée être posé. Il est ainsi donné acte au recourant de l'illicéité de sa détention.
3.2.3. Compte tenu du droit du recourant à obtenir une décision sur la légalité de sa détention en établissement carcéral pour l'ensemble de la période en cause (cf. art. 5 ch. 4 CEDH) et attendu que, sous réserve des normes fédérales, il incombe aux cantons de régler les questions d'organisation des autorités pénales cantonales d'exécution, il y a lieu de renvoyer la cause à la cour cantonale pour qu'elle désigne l'autorité compétente pour examiner les griefs du recourant tendant à son indemnisation pour l'illicéité de sa détention du 24 décembre 2015 au 11 novembre 2016 et à la constatation d'une éventuelle violation du principe de célérité, cela après avoir interpellé le DSE sur sa compétence. Au vu de ce qui précède, la cour cantonale statuera à nouveau sur les frais et dépens.
Bien qu'il ne prenne aucune conclusion en ce sens, il ressort de la motivation de son recours que le recourant s'en prend au refus de l'octroi de l'assistance judiciaire et la nomination d'un avocat d'office pour la procédure cantonale ayant conduit au prononcé de la décision du 29 juin 2016 (ACPR/396/2016). Le refus de la cour cantonale se fonde sur l'absence de chance de succès de son recours. Compte tenu de l'admission partielle du recours contre cette décision par la cour de céans, il convient de renvoyer la cause à la cour cantonale pour nouvelle décision également sur ce point.
4.
Au vu de ce qui précède, les recours doivent être partiellement admis et les arrêts attaqués annulés en relation avec le caractère illicite de la détention du 24 décembre 2015 au 11 novembre 2016 et l'indemnisation du recourant, ainsi que la violation du principe de célérité. Pour le surplus, les recours doivent être déclarés irrecevables.
Le recourant obtient partiellement gain de cause. Il peut prétendre à des dépens réduits (<ref-law>). Les demandes d'assistance judiciaires deviennent sans objet dans cette mesure (<ref-law>). Les conclusions du recourant étant, pour le surplus, dénuées de chance de succès, la demande d'assistance judiciaire est rejetée (<ref-law>). Le recourant supporte des frais réduits fixés en tenant compte de sa situation économique (art. 65 al. 2 et 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Les causes 6B_842/2016 et 6B_1377/2016 sont jointes.
2.
Les recours sont partiellement admis. Les arrêts attaqués sont annulés et les causes sont renvoyées à la cour cantonale pour nouveau jugement. Pour le surplus, les recours sont irrecevables.
3.
Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge du recourant.
4.
Le canton de Genève versera en mains du conseil du recourant une indemnité de 3000 fr. à titre de dépens.
5.
Les demandes d'assistance judiciaire sont rejetées dans la mesure où elles ne sont pas sans objet.
6.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre pénale de recours.
Lausanne, le 10 mai 2017
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Musy