Faits :
A.
A.a. Le 25 avril 2016, l'établissement pénitentiaire CURABILIS a dénoncé pénalement A._, ressortissant algérien sans domicile fixe et sans profession (P1). Il lui était reproché d'avoir, le 21 avril 2016 entre 20h00 et 20h30 à Genève, menacé un gardien de prison et d'avoir intentionnellement bouté le feu, alors qu'il se trouvait dans sa cellule de l'établissement de détention susmentionné, à ses draps et à un linge au moyen d'un briquet/cigarette, objet qu'il avait refusé d'éteindre malgré les injonctions des gardiens. Le prévenu aurait également adopté, lors de l'intervention, un comportement agressif, lançant notamment une chaise contre la porte de sa cellule. Treize personnes avaient été évacuées et il avait été fait appel à la centrale d'engagement des pompiers.
A la suite du mandat d'amener délivré contre A._, celui-ci a été appréhendé aux établissements pénitentiaires de la plaine de l'Orbe le 31 mai 2016. Il y purgeait une peine privative de liberté de 14 mois - sous déduction de 97 jours de détention provisoire et d'un jour de détention à titre de réparation morale -, ainsi qu'une peine privative de liberté de 36 mois, sous déduction de 421 jours de détention provisoire et de 5 jours de détention à titre de réparation morale. Selon l'ordre d'écrou du 4 mai 2016, le détenu avait atteint le tiers de sa peine le 13 octobre 2015 et la mi-peine au 23 juin 2016; une éventuelle libération conditionnelle était fixée au 3 mars 2017 et la fin de peine au 24 juillet 2018.
Entendu par la police, A._ a reconnu avoir mis le feu à sa cellule; il a en revanche contesté avoir voulu mettre en danger d'autres personnes, avoir adopté un comportement violent vis-à-vis des gardiens et avoir menacé l'un d'entre d'eux. Dans le cadre de l'instruction, une expertise psychiatrique - à laquelle le prévenu s'est opposée - a été ordonnée le 8 juillet 2016.
A.b. Le 18 mai 2016, le Centre hospitalier universitaire vaudois (CHUV) a déposé une plainte pénale contre A._ pour dommages à la propriété en raison des dégâts causés par le prévenu lors d'un séjour en mars 2016 dans cet établissement. Vu la procédure déjà ouverte par le Ministère public de la République et canton de Genève, cette cause lui a été transmise par les autorités pénales vaudoises.
A.c. Par ordonnance du 1er juin 2016, le Tribunal des mesures de contrainte de la République et canton de Genève (Tmc) a ordonné la détention provisoire de A._ jusqu'au 1er septembre 2016.
Cette mesure a été prolongée le 22 août 2016. Le Tmc a retenu l'existence de charges suffisantes, ainsi que des risques de fuite (nationalité étrangère, aucune attache en Suisse, peine-menace concrète) et de récidive (antécédents, facilité à adopter des comportements dangereux et/ou violents, tendances suicidaires alléguées). Le juge de première instance a également considéré qu'aucune mesure de substitution n'était susceptible d'atteindre le but de la détention. A cet égard, il a relevé que si le prévenu continuait à purger la peine de 36 mois fermes prononcée à son encontre en octobre 2015, il passerait sous l'autorité de l'Office d'exécution des peines du canton de Vaud; or, le rapport d'expertise psychiatrique pourrait mettre en lumière une maladie inconnue des autorités ayant prononcé cette sanction, ce qui permettrait au prévenu de demander la révision de son procès, respectivement de saisir la Commission des grâces du Grand Conseil vaudois.
B.
Le 16 septembre 2016, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté le recours intenté par A._ contre cette ordonnance. Elle a retenu que le prévenu avait purgé la moitié de sa peine, circonstance qui pouvait permettre aux - seules - autorités vaudoises de prononcer un régime d'exécution plus souple (travail externe, congé ou même libération conditionnelle). La cour cantonale a également relevé que, vu l'expertise psychiatrique en cours, la perspective d'une libération conditionnelle restait entière. Il en résultait, selon l'autorité précédente, que l'exécution du solde de la peine n'était pas propre à pallier le risque de fuite ou de récidive, dangers admis par le prévenu; ce dernier pouvait au demeurant voir les jours de détention provisoire subis imputés sur une éventuelle future peine, respectivement sur l'une des sanctions déjà prononcées.
C.
Par acte du 3 octobre 2016, A._ forme un recours en matière pénale contre cet arrêt, concluant à son annulation, au refus de la prolongation de la détention provisoire et, à titre subsidiaire, à sa remise en détention provisoire si l'exécution de ses peines devait prendre fin avant la clôture de la procédure P1 ou si l'exécution de sa peine ne devait plus se dérouler en milieu fermé. Il sollicite également l'octroi de l'assistance judiciaire.
La cour cantonale n'a pas formulé d'observation et le Ministère public n'a pas déposé de déterminations.

Considérant en droit :
1.
Le recours en matière pénale (<ref-law>) est ouvert contre une décision relative à la détention provisoire ou pour des motifs de sûreté au sens des <ref-law>. Le recours a été formé en temps utile (<ref-law>) contre une décision prise en dernière instance cantonale (<ref-law>). L'arrêt attaqué confirme le refus de prononcer, à titre de mesure de substitution, la poursuite de l'exécution du solde des peines privatives de liberté auxquelles le recourant a été préalablement condamné; celui-ci, prévenu et détenu, a donc un intérêt juridiquement protégé à son annulation ou à sa modification (art. 81 al. 1 let. a et b ch. 1 LTF). Vu de plus les différences de régime entre ces deux types de détention, le recourant subit également un préjudice irréparable (<ref-law>). Partant, il y a lieu d'entrer en matière.
2.
Le recourant ne conteste pas l'existence de charges suffisantes à son encontre, ainsi que celle de dangers de fuite et de récidive, conditions qui permettent en principe d'ordonner, respectivement de prolonger, la détention provisoire (art. 221 al. 1 let. a et c CPP).
Invoquant l'<ref-law>, le recourant reproche en revanche à l'autorité précédente d'avoir considéré que la poursuite de l'exécution de peines privatives de liberté prononcées précédemment à son encontre ne constituerait pas une mesure de substitution adéquate à la détention provisoire.
2.1. En vertu du principe de proportionnalité ancré à l'art. 36 al. 3 Cst., l'autorité doit tenter autant que possible de substituer à la détention toute autre mesure moins incisive propre à atteindre le même résultat (<ref-ruling> consid. 2.2 p. 276). Cette exigence est concrétisée par l'<ref-law>, qui prévoit que le tribunal compétent ordonne une ou plusieurs mesures moins sévères en lieu et place de la détention provisoire ou pour des motifs de sûreté si ces mesures permettent d'atteindre le même but que la détention. Le juge de la détention n'est en particulier pas limité par la liste énoncée à l'<ref-law> et peut également, le cas échéant, assortir la/les mesure (s) de substitution de toute condition propre à en garantir l'efficacité (arrêt 1B_165/2012 du 12 avril 2012 consid. 2.3 publié in SJ 2012 I 407).
2.2. En l'occurrence, la détention provisoire ordonnée à l'encontre du recourant tend à pallier des risques de fuite et de récidive. Selon la jurisprudence, l'exécution des peines privatives de liberté découlant de précédentes condamnations est en principe compatible avec le but de la détention provisoire, tout particulièrement lorsqu'il s'agit de prévenir les deux dangers susmentionnés (arrêts 1B_680/2012 du 6 décembre 2012 consid. 2.2 in fine; 1B_165/2012 du 12 avril 2012 consid. 2.3 publié in SJ 2012 I 407; MOREILLON/PAREIN-REYMOND, Petit commentaire, Code de procédure pénale, 2e éd. 2016, n° 5 ad <ref-law>; NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2e éd. 2013, n° 5 ad <ref-law>).
Certes, dans le cadre du régime de l'exécution des peines, l'autorité vaudoise compétente en la matière peut, dès la mi-peine et à certaines conditions, accorder au recourant un aménagement de travail externe (<ref-law>), des congés (<ref-law>), voire une éventuelle libération conditionnelle (<ref-law>). Cependant, si ces situations devaient se réaliser - ce que le recourant semble lui-même exclure vu son casier judiciaire (douze condamnations entre janvier 2009 et octobre 2015 principalement pour séjours illégaux, vols, vols par métier et en bande, infractions en matière de stupéfiants, violations de domiciles, utilisation frauduleuse d'un ordinateur, recel et infraction à la législation sur les armes) -, il n'en résulterait pas pour autant que celui-ci se trouverait remis en liberté. Dans sa décision, le juge de la détention peut en effet prévoir, à titre de condition à la mesure d'allègement, que le prévenu sera à nouveau placé en détention provisoire - ou pour motifs de sûreté selon l'avancement de la procédure - si l'exécution des sanctions précédentes, respectivement l'aménagement de celle-ci, devait entraîner sa libération préalablement à l'issue de la procédure ayant amené son placement en détention provisoire (arrêt 1B_165/2012 du 12 avril 2012 consid. 2.3 publié in SJ 2012 I 407). De plus, dès lors que l'avis d'écrou fait état de l'échéancier relatif à l'exécution de la peine, les autorités pénales genevoises paraissent à même de prendre les dispositions nécessaires pour éviter une libération, pouvant notamment s'adresser aux autorités pénales vaudoises (cf. à cet égard les dispositions en matière d'entraide judiciaire intercantonale, spécialement art. 43 al. 4, 46 al. 1 et 50 CPP). Il apparaît en conséquence que l'exécution du solde des peines privatives de liberté antérieures permet de pallier le risque de fuite.
S'agissant du risque de récidive, les actes examinés dans la présente cause ont certes été commis alors que le recourant purgeait une peine privative de liberté en milieu fermé. Il n'en demeure pas moins que le danger de réitération de l'art. 221 al. 1 let. c CPP doit s'apprécier de manière plus large en tenant compte de tous les antécédents, en l'espèce nombreux, du prévenu. Dans ces conditions, la mesure de substitution est aussi apte en l'occurrence à réduire ce danger.
2.3. Au regard de ces circonstances, la Chambre pénale de recours a violé le droit fédéral en considérant que l'exécution du solde des peines privatives de liberté prononcées préalablement à l'encontre du recourant ne constituait pas une mesure de substitution adéquate et ce grief doit être admis.
3.
Il s'ensuit que le recours est admis. L'arrêt attaqué est annulé. La cause est renvoyée à l'autorité précédente pour qu'elle ordonne, à titre de mesure de substitution à la détention provisoire, l'exécution du solde des peines privatives de liberté prononcées antérieurement à l'encontre du recourant; elle définira également à quelles conditions et dans quelles hypothèses, la détention provisoire pourrait être à nouveau ordonnée; tel serait notamment le cas si l'exécution des peines prenait fin avant la clôture de la procédure P1 ou si l'exécution de celles-ci ne devait plus se dérouler en milieu fermé.
Dès lors que les conditions permettant la détention provisoire sont réalisées, l'admission du recours n'entraîne pas la libération immédiate du recourant. Cette mesure est maintenue jusqu'à ce que le transfert du recourant en exécution de peine soit mis en oeuvre.
Le recourant, qui obtient gain de cause avec un avocat, a droit à des dépens à la charge de la République et canton de Genève (<ref-law>). Sa requête d'assistance judiciaire est donc sans objet (<ref-law>). Il n'y a pas lieu de percevoir de frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis. L'arrêt du 16 septembre 2016 de la Chambre pénale de recours de la Cour de justice de la République et canton de Genève est annulé. La cause est renvoyée à cette autorité pour qu'elle ordonne, à titre de mesure de substitution, l'exécution du solde des peines privatives de liberté prononcées antérieurement à l'encontre du recourant et procède pour son prononcé au sens des considérants. Dans l'intervalle, la détention provisoire du recourant est maintenue.
2.
La requête d'assistance judiciaire est sans objet.
3.
Une indemnité de dépens de 1'500 fr. est allouée au mandataire du recourant à la charge de la République et canton de Genève.
4.
Il n'est pas perçu de frais judiciaires.
5.
Le présent arrêt est communiqué au mandataire du recourant, au Ministère public de la République et canton de Genève et à la Chambre pénale de recours de la Cour de justice de la République et canton de Genève.
Lausanne, le 24 octobre 2016
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Fonjallaz
La Greffière : Kropf