Faits :
A.
Par jugement du 20 septembre 2018, le Tribunal d'application des peines et mesures genevois (ci-après: TAPEM) a refusé d'accorder la libération conditionnelle de X._.
B.
Par arrêt du 7 décembre 2018, la Cour de justice de la République et canton de Genève, Chambre pénale de recours, a rejeté le recours formé par X._ contre cette décision.
La cour cantonale a retenu en substance les faits suivants.
B.a. X._, ressortissant français né en 1971, a été condamné le 30 septembre 1991 par la Cour d'assises pour mineurs de Grenoble à une peine privative de liberté de 5 ans pour avoir, de concert avec son frère, tué son père en le frappant à plusieurs reprises durant son sommeil, à coups de couteau et de crosse de carabine.
X._ a été condamné le 17 septembre 2004, par la Cour d'assises de Genève, à la réclusion à vie pour assassinat, faux dans les titres, faux dans les certificats, escroquerie par métier, utilisation frauduleuse d'un ordinateur et vol. Malgré les dénégations de X._, il avait alors été retenu que, pour empêcher la découverte de malversations commises au détriment de la fiduciaire qui l'employait, à hauteur de plusieurs centaines de milliers de francs, il avait frappé un comptable de l'entreprise par derrière avec un outil puis, alors que sa victime se trouvait à terre, s'était acharné sur elle, la frappant à de très nombreuses reprises dans la région du cou avec un outil tranchant. Une fois sa victime achevée, dans le but manifeste d'égarer les enquêteurs, il avait partiellement dévêtu le corps pour y inscrire les mots " sale violeur ".
Le 10 décembre 2009, le prénommé a été condamné par la Cour d'assises de la Haute-Savoie, pour tentative d'assassinat et vol avec violence ayant entraîné une infirmité permanente ou une mutilation, à la réclusion criminelle à perpétuité, avec une période de sûreté de 22 ans.
B.b. Interrogé par des experts psychiatres sur la manière dont le premier meurtre avait été conçu, X._ avait répondu " c'est arrivé aussi bêtement, avec mon frère (...) comme si on avait décidé d'une partie de tennis (...) on en a parlé dans l'après-midi (...) si on tuait notre père (...) on l'a tué le soir ". Les experts avaient alors conclu que X._ était un sujet très influençable et excessivement immature, au fonctionnement éminemment égocentrique.
L'expert psychiatre qui s'était penché sur son cas en 2007 avait relevé que X._ l'avait impressionné, tant par sa froideur hors du commun lorsqu'il lui avait relaté l'assassinat de son père que par son déni de responsabilité. En l'absence d'éléments psychotiques, il fallait admettre l'existence d'une personnalité perverse comme on en rencontre rarement, sur laquelle la sanction n'avait eu aucun effet. Sa dangerosité était inhérente à la structure de sa personnalité et le pronostic redoutable, l'expert se disant très réservé sur la possibilité d'une mesure thérapeutique quelconque ou d'une mesure de rééducation.
Le Service de probation et d'insertion du canton de Genève (ci-après: SPI) a procédé à une évaluation criminologique approfondie entre le 24 mai et le 21 juillet 2017 et a noté que X._ présentait une personnalité faisant montre d'un noyau narcissique et d'une déficience émotionnelle ayant des caractéristiques communes avec les personnes diagnostiquées psychopathes. Le risque de récidive était considéré comme faible à modéré en milieu protégé, telle la détention, mais pouvait être revu à la hausse, notamment dans une situation où l'intéressé se sentirait menacé, tension qui pouvait aboutir à un " déclic " et dont la solution serait l'élimination de l'obstacle. Dans un milieu non protégé, l'on pouvait raisonnablement conjecturer un risque de récidive violente décuplé, compte tenu d'éléments statiques particulièrement significatifs, tels ses antécédents de violence et de comportement antisociaux ainsi que l'absence de stratégie mise en oeuvre afin de pallier les problématiques constituant ses divers passages à l'acte.
B.c. Sur la base de ces éléments, le Service d'application des peines et mesures (ci-après: SAPEM) a, le 23 août 2017, préavisé défavorablement la libération conditionnelle, soulignant le peu, voire l'absence d'effet de quinze années de détention sur le positionnement de l'intéressé et le risque de récidive considéré comme élevé par l'ensemble des experts. Le ministère public a lui aussi préavisé négativement la demande.
Entendu par le TAPEM le 19 septembre 2017, X._ a reconnu qu'une avocate française s'était proposée de l'assister pour demander la confusion des peines en France, mais avait affirmé n'avoir fait aucune démarche en ce sens. Par décision du même jour, le TAPEM a ordonné la suspension de la cause dans l'attente d'une expertise psychiatrique confiée au Centre universitaire romand de médecine légale (ci-après: CURML), d'une évaluation criminologique complète, du préavis de la commission d'évaluation de la dangerosité (ci-après: CED) et, sur cette base, de nouveaux préavis de la prison, du SAPEM et du ministère public.
B.c.a. Dans leur rapport du 25 avril 2018, les experts du CURML ont posé le diagnostic de trouble mixte de la personnalité, comprenant des traits psychopathiques, narcissiques et pervers, constitutifs d'un grave trouble mental. Le potentiel de violence de l'expertisé était le même qu'en 2002 et le risque de récidive devait être considéré comme moyen à élevé, en particulier en raison des dimensions psychopathologique et perverse de sa personnalité, de ses faibles capacités de remise en question, de la rigidité de son fonctionnement psychique, de l'absence délibérée de démarche de soin et des passages à l'acte prémédités, avec une impossibilité de " retour en arrière ". Une mesure de soin était susceptible de limiter ce risque, même si le potentiel d'évolution favorable était faible en raison de l'âge de l'intéressé et de son absence de soin jusqu'alors. Un internement leur paraissait indispensable.
B.c.b. Le 22 mai 2018, le SPI a complété son évaluation du 21 juillet 2017 en soulignant que l'expertise corroborait en grande partie ses propres constats, tant dans l'analyse de la structure de la personnalité de l'intéressé que dans l'évaluation de son risque de récidive violente actuel.
B.c.c. Sur la base des pièces du dossier, X._ ayant refusé de comparaître devant elle, la CED a estimé que ce dernier présentait un danger élevé pour la collectivité dans le cadre de l'octroi de la libération conditionnelle.
B.c.d. Le SAPEM a maintenu son préavis négatif. La demande de révision de l'arrêt de la Cour d'assises du 17 septembre 2004 formée par le ministère public le 3 août 2018 aux fins de prononcer l'internement de X._ en cours d'exécution de la peine a été rejetée par arrêt de la Chambre pénale d'appel et de révision de la Cour de justice du 24 septembre 2018. La cause est actuellement pendante devant le Tribunal fédéral.
B.d. X._ n'a pas souhaité se présenter à l'audience du 20 septembre 2018 devant le TAPEM, lors de laquelle les experts ont confirmé leur rapport du 25 avril 2018. Ils ont relevé que le risque de récidive, qualifié de moyen à élevé en cas de libération conditionnelle, était probablement moins important en détention qu'à l'extérieur.
C.
X._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt cantonal du 7 décembre 2018. Il conclut, avec suite de frais et dépens, à l'annulation de l'arrêt et au renvoi de la cause à la cour cantonale pour qu'elle prononce la libération conditionnelle du recourant, sous condition suspensive de son transfèrement en France aux fins d'exécution de la peine prononcée à son encontre le 10 décembre 2009 par la Cour d'Assises de la Haute-Savoie. Il requiert le bénéfice de l'assistance judiciaire.

Considérant en droit :
1.
Le recours s'ouvre sur un exposé des faits, sans aucune motivation justifiant en quoi les conditions de l'<ref-law> seraient remplies. Il n'y a pas lieu de s'y arrêter.
2.
Le recourant reproche à la cour cantonale d'avoir confirmé le refus de la libération conditionnelle en violation de l'<ref-law>, dès lors qu'elle aurait fait fi de sa situation extraordinaire.
2.1. Aux termes de l'<ref-law>, l'autorité compétente libère conditionnellement le détenu qui a subi les deux tiers de sa peine, mais au moins trois mois de détention, si son comportement durant l'exécution de la peine ne s'y oppose pas et s'il n'y a pas lieu de craindre qu'il ne commette de nouveaux crimes ou de nouveaux délits. La libération conditionnelle constitue la dernière étape de l'exécution de la sanction pénale. Elle est la règle et son refus l'exception, dans la mesure où il n'est plus exigé qu'il soit à prévoir que le condamné se conduira bien en liberté (cf. art. 38 ch. 1 al. 1 aCP), mais seulement qu'il ne soit pas à craindre qu'il commette de nouveaux crimes ou délits. Autrement dit, il n'est plus nécessaire pour l'octroi de la libération conditionnelle qu'un pronostic favorable puisse être posé. Il suffit que le pronostic ne soit pas défavorable (<ref-ruling> consid. 2.2 et 2.3 p. 203 s.). Le pronostic à émettre doit être posé sur la base d'une appréciation globale, prenant en considération les antécédents de l'intéressé, sa personnalité, son comportement en général et dans le cadre des délits qui sont à l'origine de sa condamnation, le degré de son éventuel amendement ainsi que les conditions dans lesquelles il est à prévoir qu'il vivra (<ref-ruling> consid. 2.3 p. 203 s. et les arrêts cités). La nature des délits commis par l'intéressé n'est, en tant que telle, pas à prendre en compte, en ce sens que la libération conditionnelle ne doit pas être exclue ou rendue plus difficile pour certains types d'infractions. Toutefois, les circonstances dans lesquelles l'auteur a encouru la sanction pénale sont également pertinentes dans la mesure où elles sont révélatrices de sa personnalité et donnent ainsi certaines indications sur son comportement probable en liberté. Au demeurant, pour déterminer si l'on peut courir le risque de récidive, inhérent à toute libération qu'elle soit conditionnelle ou définitive, il faut non seulement prendre en considération le degré de probabilité qu'une nouvelle infraction soit commise mais également l'importance du bien qui serait alors menacé. Ainsi, le risque de récidive que l'on peut admettre est moindre si l'auteur s'en est pris à la vie ou à l'intégrité corporelle de ses victimes que s'il a commis par exemple des infractions contre le patrimoine (<ref-ruling> consid. 2a p. 115 s.).
Dans l'émission du pronostic, l'autorité compétente dispose d'un large pouvoir d'appréciation. Le Tribunal fédéral n'intervient que si elle en a abusé, notamment lorsqu'elle a omis de tenir compte de critères pertinents et s'est fondée exclusivement sur les antécédents du condamné (<ref-ruling> consid. 2.3 p. 204).
2.2. En substance, la cour cantonale a notamment tenu compte de la dangerosité du recourant ainsi que du risque de récidive d'actes de nature violente, considéré comme faible à modéré - mais non nul - en milieu carcéral et comme moyen à élevé en liberté. Elle a également relevé que la dangerosité avait pour origine les traits psychopathiques, narcissiques et pervers de la personnalité du recourant et que seul un traitement thérapeutique de longue haleine était à même de réduire la menace qu'il représentait pour la société. La cour cantonale a rappelé que le recourant n'avait pas indemnisé ses victimes, ni initié un traitement et qu'il persistait à ne pas vouloir se remettre en cause.
Fondée sur ces constats ainsi que sur les antécédents du recourant, son absence de prise de conscience et l'importance du bien juridique menacé, la cour cantonale ne pouvait qu'émettre un pronostic défavorable et constater que les conditions de l'<ref-law> n'étaient pas réalisées.
2.3. Le recourant ne remet pas en cause le risque de récidive retenu en lien avec des actes de violence (tant en détention qu'en liberté), son absence de prise de conscience, son refus d'initier un traitement et ses diagnostics psychiatriques. Il se borne à affirmer que la cour cantonale n'aurait pas tenu compte des circonstances exceptionnelles du cas d'espèce, en ce sens qu'il fait l'objet d'une condamnation à une réclusion à perpétuité en France, de sorte qu'il purgerait sa peine dans ce pays une fois " libéré ".
Or il est rappelé que si le risque de récidive a été qualifié de moyen à élevé en liberté, il n'était pas nul en milieu protégé, au contraire. Qualifié de faible à modéré, le risque pouvait même être revu à la hausse si le recourant se sentait menacé. En ce sens, les conditions dans lesquelles le recourant prétend vivre en cas de " libération conditionnelle " ne lui sont d'aucun secours.
En tout état, il est sans pertinence, au vu du but de la libération conditionnelle, qui est de favoriser la réinsertion de l'intéressé par le réapprentissage de la vie en liberté, que le recourant fasse l'objet d'une condamnation à une réclusion à perpétuité en France (cf. <ref-ruling> consid. 2.3 p. 203; <ref-ruling> consid. 3 p. 195; arrêt 6B_428/2009 du 9 juillet 2009 consid. 1.3). Au contraire, la libération conditionnelle constitue la dernière étape de l'exécution de la sanction pénale en vue de la réinsertion et non un moyen de transfert d'établissement pénitentiaire. Admettre une libération conditionnelle pour ce motif viderait de son sens le principe même et ses modalités d'exécution (cf. art. 86 à 89 CP) ainsi que la possibilité de révoquer cette dernière en cas d'échec de la mise à l'épreuve (<ref-law>). Aussi, le recourant ne saurait exiger, sous couvert d'une violation de l'<ref-law>, son transfert d'établissement pénitentiaire, respectivement son extradition.
En définitive, le recourant ne saurait rien déduire en sa faveur de la " circonstance exceptionnelle " qu'il réalise par une double condamnation à la réclusion à vie pour la commission, entre autres infractions, de deux assassinats (l'un resté au stade de la tentative).
Pour le reste, le recourant ne développe aucun grief suffisamment motivé sous l'angle de l'art. 3 CEDH (art. 42 al. 2 et 106 al. 2 LTF).
3.
Le recours doit être rejeté dans la mesure où il est recevable. Comme il était dénué de chances de succès, la demande d'assistance judiciaire doit être rejetée (<ref-law>). Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>), dont le montant sera fixé en tenant compte de sa situation financière.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La demande d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1'200 fr., sont mis à la charge du recourant.
4.
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 21 février 2019
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke