Faits :
A.
A.a. A._, né en 1966, a effectué un premier séjour en Suisse entre 1990 et 1993 dans le cadre d'une procédure d'asile. En mars 1994, il y a déposé une deuxième demande d'asile, qu'il a retirée en septembre de la même année après avoir obtenu une autorisation de séjour suite à son mariage avec une ressortissante étrangère au bénéfice d'un permis d'établissement. Une fille, B._, est née de cette union le 1er juillet 1994. Les époux ont divorcé en septembre 1998. L'intéressé a eu deux autres filles, C._ et D._, nées respectivement le 3 juillet 2001 et le 17 juillet 2002, avec sa seconde épouse, dont il est divorcé depuis 2009. Ces deux filles ont la nationalité suisse (<ref-law>).
A.b. Le 12 août 2013, après avoir sommé à plusieurs reprises l'intéressé d'améliorer sa situation financière, le Service des migrations de la République et du canton de Neuchâtel (ci-après: le Service des migrations) lui a refusé la prolongation de son autorisation de séjour au motif de sa dépendance à l'aide sociale et de son endettement important.
Le 4 février 2015, constatant que le Service des migrations avait retenu à tort comme pays d'origine de l'intéressé la République démocratique du Congo et non la République du Congo (Brazzaville), le Département de l'économie et de l'action sociale de la République et du canton de Neuchâtel (ci-après: le Département) a partiellement admis le recours interjeté par l'intéressé contre la décision du 12 août 2013 et renvoyé la cause au Service des migrations pour nouvelle décision. Par décision du 14 avril 2015, le Service des migrations a confirmé la non-prolongation de l'autorisation de séjour et le renvoi de Suisse de l'intéressé. Le Département, puis la Cour de droit public du Tribunal cantonal de la République et du canton de Neuchâtel (ci-après: le Tribunal cantonal) ont rejeté les recours de l'intéressé par décision du 31 août 2015 respectivement par arrêt du 17 novembre 2016. Dans le cadre de son examen, le Tribunal cantonal a notamment procédé à une pesée des intérêts au sens des art. 96 LEtr (depuis le 1er janvier 2019 : LEI) et 8 § 2 CEDH. Cette décision n'a pas été contestée et est entrée en force.
B.
Le 22 décembre 2016, l'intéressé a déposé une demande de reconsidération auprès du Service des migrations en invoquant une procédure en modification du jugement de divorce en cours portant sur le transfert de la garde de ses deux filles mineures à lui-même, leur père, et le versement en ses mains des allocations familiales perçues pour elles par son ex-épouse. Par décision du 30 janvier 2017, le Service des migrations a déclaré irrecevable cette demande de reconsidération au motif que l'intéressé avait agi tardivement, puisque les faits nouveaux invoqués auraient pu être présentés dans le cadre de la procédure de recours menée devant le Tribunal cantonal.
Le 6 juin 2019, le Département a admis le recours interjeté par l'intéressé contre cette décision et renvoyé la cause au Service des migrations pour nouvelle décision, après avoir relevé que le transfert de la garde au père était devenu effectif à l'entrée en force du jugement en modification du jugement de divorce, le 21 août 2017, et que cela représentait un fait nouveau susceptible de justifier un réexamen.
Par décision du 9 octobre 2019, le Service des migrations a rejeté la demande de reconsidération. Il a notamment retenu que la fille de l'intéressé, C._, était majeure et n'invoquait pas de lien de dépendance avec son père, de sorte que celui-ci ne pouvait pas se prévaloir de la relation qu'il entretenait avec elle pour se voir octroyer une autorisation de séjour sous l'angle de l'article 8 CEDH. S'agissant de sa fille D._, le Service des migrations, après avoir reconnu que l'intéressé entretenait avec elle une relation étroite et effective puisqu'ils vivaient en ménage commun, a considéré au terme d'une pesée des intérêts que l'intérêt public à l'éloignement de l'intéressé l'emportait sur son intérêt privé à pouvoir vivre en Suisse.
Statuant sur recours, le Département a confirmé cette décision le 14 janvier 2020. Par arrêt du 7 juin 2021, le Tribunal cantonal a rejeté le recours interjeté par l'intéressé contre la décision sur recours précitée, après avoir relevé que les deux filles de celui-ci étaient majeures et qu'il ne pouvait partant pas se prévaloir de l'article 8 CEDH pour se voir octroyer une autorisation de séjour par regroupement familial inversé.
C.
Agissant par le biais du recours en matière de droit public et subsidiairement par celui du recours constitutionnel, A._ demande au Tribunal fédéral, sous suite de frais et dépens, outre l'effet suspensif et l'assistance judiciaire, l'annulation de l'arrêt précité du 7 juin 2021 et la prolongation de son autorisation de séjour.
L'effet suspensif a été accordé par ordonnance présidentielle du 12 juillet 2021.
Il n'a pas été ordonné d'échange d'écritures.

Considérant en droit :
1.
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions dans le domaine du droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Selon la jurisprudence, il suffit, sous l'angle de la recevabilité, qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas et que, partant, la voie du recours en matière de droit public soit ouverte (cf. <ref-ruling> consid. 1.1).
En l'espèce, le recourant invoque l'art. 8 CEDH. Son séjour légal de plus de dix ans en Suisse est potentiellement de nature à lui conférer un droit à l'obtention d'une autorisation de séjour sous l'angle du droit au respect de sa vie privée (cf. <ref-ruling> consid. 3.9). Le recours échappe donc au motif d'irrecevabilité prévu à l'art. 83 let. c ch. 2 LTF, étant précisé que le point de savoir si le recourant remplit les conditions pour obtenir l'autorisation requise relève du fond et non de la recevabilité (cf. <ref-ruling> consid. 1.1). La voie du recours en matière de droit public est ainsi ouverte, ce qui entraîne l'irrecevabilité du recours constitutionnel subsidiaire formé en parallèle par l'intéressé (<ref-law> a contrario).
1.2. Les autres conditions de recevabilité du recours en matière de droit public sont également réunies (cf. art. 42, 82 let. a, 86 al. 1 let. d et al. 2, 89 al. 1, 90 et 100 al. 1 LTF), si bien qu'il convient d'entrer en matière.
2.
2.1. Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), alors qu'il n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par le recourant, conformément au principe d'allégation (<ref-law>). Dans ce cas, l'acte de recours doit contenir un exposé succinct des droits fondamentaux violés et préciser en quoi consiste la violation (cf. <ref-ruling> consid. 1.3).
2.2. Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits constatés par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law>. Selon l'<ref-law>, le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire - ou en violation du droit au sens de l'<ref-law> et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-ruling> consid. 6; <ref-ruling> consid. 1.6). Conformément à l'<ref-law>, la partie recourante doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. A défaut, il n'est pas possible de tenir compte d'un état de fait qui diverge de celui qui est contenu dans l'acte attaqué (<ref-ruling> consid. 5.1; arrêt 2C_793/2018 du 13 mars 2019 consid. 2).
En l'occurrence, dans la mesure où le recourant présente une argumentation partiellement appellatoire, en complétant ou en modifiant librement l'état de fait retenu dans l'arrêt entrepris, sans invoquer ni l'arbitraire, ni une constatation manifestement inexacte des faits, le Tribunal fédéral ne peut pas en tenir compte. Il statuera donc sur la base des faits tels qu'ils ressortent de l'arrêt attaqué.
3.
Le recourant invoque l'art. 8 CEDH, essentiellement sous l'angle du respect de la vie familiale en se prévalant de la relation qu'il entretient avec ses deux filles cadettes de nationalité suisse.
3.1. En l'occurrence, les filles du recourant sont majeures et il ne fait valoir aucun rapport de dépendance particulier avec elles. Le recourant ne peut ainsi pas déduire de droit de l'art. 8 CEDH en lien avec sa vie familiale, ni d'ailleurs de l'art. 13 Cst. qu'il invoque également dans ce cadre (cf. <ref-ruling> consid. 3.1; <ref-ruling> consid. 6.1; arrêts 2C_279/2021 du 16 novembre 2021 consid. 4.2; 2C_433/2021 du 21 octobre 2021 consid. 6.1 et autres références citées). En outre, comme le relève à juste titre l'autorité précédente, la durée de la procédure de réexamen, dont le point de départ peut être fixé au 21 août 2017, ne peut être qualifiée d'exagérément longue et les enfants concernés étaient déjà majeurs avant le dépôt du recours devant le Tribunal fédéral. La pratique retenant comme déterminant l'âge atteint par l'enfant au moment où le Tribunal fédéral statue n'a partant pas à être remise en question (cf. <ref-ruling> consid. 6.7 s.; arrêt 2C_326/2019 du 3 février 2020 consid. 2.2.4).
Ce qui précède est toutefois sans incidence dans le présent cas. En effet, l'intéressé, qui réside en Suisse depuis plus de dix ans, peut se prévaloir d'un droit à séjourner dans ce pays fondé sur la protection de la vie privée garantie par l'art. 8 CEDH (cf. <ref-ruling> consid. 3; arrêt 2C_668/2021 du 20 décembre 2021 consid. 6.1 et références). Les arrêts de la CourEDH qu'il cite en lien avec la protection de la vie familiale pour justifier l'application de cette disposition sont dès lors sans pertinence.
4.
Reste à examiner si le refus de prolonger l'autorisation de séjour du recourant est conforme au principe de la proportionnalité tiré de l'art. 8 par. 2 CEDH.
4.1. Au demeurant, contrairement à ce que soutient le Tribunal cantonal, une pesée complète des intérêts en présence s'impose aussi lorsque l'autorité inférieure est, comme en l'espèce, entrée en matière sur la demande de reconsidération (cf. arrêts 2C_203/2020 du 8 mai 2020 consid. 4.3; 2C_107/2018 du 19 septembre 2018 consid. 3.3). Selon les circonstances, une motivation succincte est alors possible (cf. arrêt 2C_203/2020 du 8 mai 2020 consid. 4.5).
Dans le présent cas, le Tribunal cantonal a toutefois implicitement procédé à une telle pesée en examinant si les nouveaux éléments apportés par le recourant étaient susceptibles de modifier la pesée des intérêts réalisée dans son arrêt du 17 novembre 2016, ce qu'il a nié.
4.2. L'art. 8 par. 2 CEDH suppose de tenir compte de l'ensemble des circonstances et de mettre en balance l'intérêt privé à l'obtention d'un titre de séjour et l'intérêt public à son refus (<ref-ruling> consid. 4.2; <ref-ruling> consid. 3.1; <ref-ruling> consid. 2.1; <ref-ruling> consid. 2.4). Dans ce cadre, les liens familiaux du recourant notamment ceux tissés avec ses filles majeures peuvent entrer en ligne de compte (cf. arrêt de la CourEDH, Hasanbasic c. Suisse du 11 juin 2013, requête n° 52166/09, § 60 in fine).
4.3. En l'occurrence, on peut retenir en défaveur du recourant, en premier lieu, une dépendance durable à l'aide sociale (près de 400'000 fr. selon la décision du Service des migrations du 9 octobre 2019; <ref-law>), en dépit d'avertissements répétés du Service des migrations, qui est imputable à l'intéressé et représente, par ailleurs, un motif sérieux de ne pas renouveler son autorisation de séjour (cf. <ref-ruling> consid. 3; arrêt 2C_674/2020 du 20 octobre 2020 consid. 3). Il a en outre fait l'objet de cinq condamnations pénales entre décembre 1996 et mars 2012, à des peines de travail d'intérêt général (80 heures), de jours-amende (pour un total de 18 jours) et de prison (pour un total de 25 jours), pour infraction à la LCR, vol d'usage et conduite sans permis, instigation à faux dans les certificats, voies de fait, injures, violence ou menace contre les autorités et les fonctionnaires (<ref-law>). Enfin, il présente un faible degré d'intégration sur le plan socio-culturelle et très faible sur le plan professionnel (cf. arrêt du Tribunal cantonal du 17 novembre 2016 consid. 3b; <ref-law>).
Les éléments en faveur du recourant, comme la longue durée de son séjour en Suisse, ainsi que la présence de ses filles dans ce pays, ne sauraient contrebalancer ce qui précède. Il ressort d'ailleurs à cet égard de l'arrêt attaqué que les relations qu'il entretient avec celles-ci ne vont pas au-delà des relations normales et usuelles qui peuvent lier des parents avec leurs enfants devenus jeunes adultes.
Un retour dans son pays d'origine est de plus exigible de la part du recourant et les visites et les moyens de communication modernes lui permettront de maintenir des contacts réguliers avec les membres de sa famille vivant en Suisse. Au surplus, dans l'arrêt querellé, le Tribunal cantonal a relevé que le syndrome fibromyalgique diagnostiqué en 2018 ne représentait pas une modification de la situation puisque les douleurs qui avaient incité les médecins à poser ce diagnostic étaient déjà présentes au moment où l'arrêt du Tribunal cantonal du 17 novembre 2016 a été rendu et avaient déjà été reconnues par les médecins examinateurs comme l'expression d'une fibromyalgie. Le recourant invoque de façon appellatoire que ses problèmes de santé l'auraient contraint à bénéficier de l'aide sociale et que ceux-ci ne pourront pas être efficacement traités dans son pays d'origine, ce qui n'est pas admissible (cf. supra consid. 2.2). Ces éléments de fait ne peuvent partant pas être pris en compte par le Tribunal fédéral. Enfin, les arrêts de la CourEDH qu'il cite ne lui sont d'aucune aide, car ils reposent sur des états de faits différents. En particulier, dans l'arrêt Hasanbasic c. Suisse et contrairement au cas d'espèce, l'étranger concerné était né en Suisse, il avait non seulement des enfants majeurs dans ce pays, mais également son épouse, titulaire d'un permis d'établissement et tous deux y disposaient d'une intégration sociale importante.
Sur le vu de ces éléments, on ne voit pas que le refus de prolongation de l'autorisation de séjour du recourant serait disproportionné et partant contraire à l'art. 8 CEDH. L'intérêt public à l'éloignement du recourant de Suisse prime ses intérêts privés, ainsi que ceux de ses filles, à le voir demeurer dans ce pays.
5.
Les considérants qui précèdent conduisent au rejet du recours en matière de droit public et à l'irrecevabilité du recours constitutionnel subsidiaire. Le recours étant d'emblée dénué de chance de succès, la demande d'assistance judiciaire est rejetée (cf. <ref-law>). Succombant, le recourant doit supporter les frais judiciaires (cf. <ref-law>), qui seront toutefois fixés en tenant compte de sa situation financière (cf. <ref-law>). Il n'est pas alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours en matière de droit public est rejeté.
2.
Le recours constitutionnel subsidiaire est irrecevable.
3.
La requête d'assistance judiciaire est rejetée.
4.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
5.
Le présent arrêt est communiqué au mandataire du recourant, au Service des migrations du canton de Neuchâtel, au Département de l'économie et de l'action sociale et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, ainsi qu' au Secrétariat d'Etat aux migrations.
Lausanne, le 7 mars 2022
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
La Présidente : F. Aubry Girardin
Le Greffier : A. de Chambrier