Faits : A. A.a. Incarcéré le 21 juillet 2015, X._ a été condamné par jugement du 16 septembre 2016 du Tribunal correctionnel de la République et canton de Genève, pour infraction grave à la LStup et séjour illégal, à une peine privative de liberté de quatre ans et demi. Statuant sur demande de X._, le Tribunal d'application des peines et mesures (ci-après : TAPEM) a, par jugement du 11 juillet 2018, ordonné sa libération avec effet au jour de son renvoi de Suisse, au plus tôt le 18 juillet 2018. Il ressort de ce jugement que le prénommé a fait l'objet d'une décision de renvoi de Suisse en date du 12 juin 2009 (entrée en force le 24 juin 2009). Le 5 août 2018, X._ n'est pas revenu de son congé et a quitté le territoire suisse pour gagner l'Espagne. En réponse à un courrier de X._ dans lequel celui-ci prétendait avoir exécuté la décision de renvoi de juin 2009, le Service de l'application des peines et mesures (ci-après : SAPEM) a, par courrier du 10 septembre 2018, indiqué qu'au vu de son non-retour de congé, celui-ci demeurait en arrestation pour un solde de peine d'un an, cinq mois et 13 jours. Le SAPEM a joint à cet envoi l'ordre d'exécution " Ripol " du même jour, adressé à la prison de Champ-Dollon. Il a en outre refusé de restituer à l'intéressé ses documents d'identité et d'autres effets personnels ainsi que de solder ses comptes. A.b. Le 24 septembre 2018, X._ a formé recours contre l'ordre d'exécution de peine du 10 septembre 2018 par lequel le SAPEM avait requis sa détention. Il a également formé recours contre la décision du SAPEM du même jour, lui signifiant avoir ordonné son arrestation en raison de son non-retour de congé du 5 août 2018 et refusant de lui restituer ses effets personnels ainsi que de solder ses comptes. Par arrêt du 2 octobre 2018, la Chambre pénale de recours de la Cour de justice genevoise a rejeté ce recours, dans la mesure de sa recevabilité, ainsi que la demande d'assistance judiciaire et de désignation d'un avocat d'office. Elle a condamné X._ au paiement des frais de la procédure de recours. Par arrêt du 30 janvier 2019, le Tribunal fédéral a admis le recours en matière pénale formé par X._ contre l'arrêt du 2 octobre 2018, a annulé l'arrêt attaqué et a renvoyé la cause à la cour cantonale afin qu'elle annule les ordres d'exécution de peine et d'arrestation du 10 septembre 2018 (arrêt 6B_1121/2018). La cour cantonale était également invitée à examiner à nouveau la question de la restitution de ses effets personnels et du solde de ses comptes (consid. 2 in fine) et la question de l'assistance judiciaire (consid. 3). En substance, le Tribunal fédéral a considéré qu'à partir du moment où le recourant avait quitté le territoire suisse après le 18 juillet 2018, le renvoi n'avait plus à être exécuté par une autorité. Il en a déduit que le recourant se trouvait au bénéfice d'une libération conditionnelle, conformément au jugement du TAPEM du 11 juillet 2018. Statuant sur renvoi par arrêt du 10 avril 2019 (procédure xxx), la Chambre pénale de recours de la Cour de justice genevoise a annulé les ordres d'exécution de peine et d'arrestation délivrés par le SAPEM et a ordonné la restitution à X._ de ses effets personnels. Elle lui a désigné un avocat d'office, auquel elle a alloué une indemnité de 1'992 fr. 45 à la charge de l'Etat, et a laissé les frais de la procédure de recours à la charge de l'Etat. A.c. Le 11 septembre 2018, X._ a formé une "requête en interprétation" (cf. art. 83 CPP), subsidiairement, une demande de révision auprès du TAPEM, en lien avec sa décision du 11 juillet 2018. Par décision du 15 octobre 2018, le TAPEM a refusé de donner suite à cette requête. Le 26 octobre 2018, X._ a recouru contre la décision du TAPEM, concluant, avec suite de frais et dépens, à son annulation et à ce que le point 1 du dispositif du jugement du 11 juillet 2018 soit interprété en ce sens qu'il jouissait pleinement de la libération conditionnelle accordée à cette date. Il a sollicité en outre l'assistance judiciaire et la désignation de son conseil comme défenseur d'office. Par courrier du 11 février 2019, la Chambre pénale de recours de la Cour de justice genevoise a invité le conseil de X._ à lui indiquer s'il maintenait son recours du 26 octobre 2018, dans la mesure où, eu égard à l'arrêt du Tribunal fédéral du 30 janvier 2019, celui-ci semblait être devenu sans objet. Le conseil a indiqué qu'il adhérait au fait que son recours du 26 octobre 2018 ne méritait plus d'être tranché sur le fond. Les frais devaient être laissés à la charge de l'Etat, l'assistance judiciaire devait être accordée à son client et un avocat d'office devait lui être désigné dans le cadre du recours. B. Par arrêt du 10 avril 2019, la Cour de justice de la République et canton de Genève, Chambre pénale de recours, a déclaré le recours sans objet et a rayé la cause du rôle. Elle a rejeté la demande d'assistance juridique et condamné X._ aux frais de la procédure de recours, comprenant un émolument de 500 francs. C. X._ forme un recours en matière pénale auprès du Tribunal fédéral contre cet arrêt du 10 avril 2019 et conclut, avec suite de frais et dépens, à son annulation en tant qu'il est condamné aux frais de la procédure cantonaux et dans la mesure où le bénéfice de l'assistance juridique lui est refusé. Il requiert que les frais de procédure soient laissés à la charge du canton de Genève et qu'il soit mis au bénéfice de la défense d'office dans le cadre de la procédure de recours, une indemnité de 2'369 fr. 40 lui étant allouée. Subsidiairement, le recourant conclut au renvoi de la cause à la cour cantonale pour qu'elle fixe l'indemnité. Le recourant requiert le bénéfice de l'assistance judiciaire dans le cadre de la procédure fédérale. D. Invités à se déterminer sur le recours, la cour cantonale s'est référée à son arrêt tandis que le TAPEM n'a pas présenté d'observation dans le délai imparti.