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 (art. 134 CP), vol (art. 139 CP), tentative de vol (art. 22 et 139 CP), dommages à la propriété (art. 144 CP), violation de domicile (art. 186 CP) et consommation de stupéfiants (art. 19a LStup). 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'art. 61 CP, 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'art. 61 CP 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 (art. 61 CP), ordonné la poursuite de cette mesure, ainsi que de celle de l'art. 63 CP 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'art. 61 CP, 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'art. 63 CP 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'art. 61 CP 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'art. 61 CP 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'art. 61 CP, à 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.