Faits :
A.
X._, ressortissant kosovar, né en 1967, a travaillé en Suisse comme saisonnier de 1990 à 1998, puis a déposé une demande d'asile rejetée par l'Office fédéral des réfugiés le 12 octobre 1999. Dans son pays d'origine, X._ a eu trois enfants, nés en 1994, 1997 et 2000, avec son ex-épouse, dont il a divorcé le 11 mars 2004.
Le 26 octobre 2006, X._ s'est marié dans le canton de Neuchâtel avec une ressortissante suisse, Y._, née en 1964, et a obtenu une autorisation de séjour, régulièrement renouvelée jusqu'au 26 octobre 2009. Avisé que le couple vivait séparé depuis mi-septembre 2008 et que le divorce des époux avait été prononcé le 7 septembre 2010, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a refusé de prolonger l'autorisation de séjour de X._, par décision du 13 décembre 2011. Les recours formés par l'intéressé contre cette décision ont été rejetés, tant par le Département de l'économie du canton de Neuchâtel, devenu Département de l'économie et de l'action sociale (ci-après: le Département), par décision du 3 octobre 2012, que par la Cour de droit public du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal), par arrêt du 22 mai 2013.
B.
X._ a formé auprès du Tribunal fédéral un recours en matière de droit public, subsidiairement un recours constitutionnel subsidiaire.
Par arrêt du 20 novembre 2013 (2C_580/2013), le Tribunal fédéral a admis le recours en matière de droit public dans la mesure où il était recevable, annulé l'arrêt attaqué et renvoyé l'affaire au Tribunal cantonal pour nouvelle décision dans le sens des considérants. Partant, il a déclaré irrecevable le recours constitutionnel subsidiaire. Le Tribunal fédéral a retenu en bref que les premiers juges avaient arbitrairement refusé d'examiner les griefs du recourant concernant l'application des art. 50 al. 1 let. a de la loi fédérale sur les étrangers (LEtr; RS 142.20) et 8 CEDH pour le motif que le recourant ne s'était pas prévalu de ces dispositions devant le Département, lequel les avait pourtant examinées brièvement. Il a ainsi jugé la position de l'instance inférieure d'autant plus insoutenable que son rôle, en tant qu'autorité de recours, était précisément de vérifier si la décision attaquée devant elle était ou non fondée. A cela s'ajoutait que, selon l'<ref-law>, l'autorité qui précède immédiatement le Tribunal fédéral doit pouvoir examiner au moins les griefs visés aux art. 95 à 98 LTF, de sorte que la limitation du pouvoir d'examen que s'était imposée le Tribunal cantonal était également contraire à cette disposition.
Par arrêt du 4 février 2014, le Tribunal cantonal a rejeté le recours et mis les frais à la charge du recourant. Il a considéré que la première exigence de l'art. 50 al. 1 let. a LEtr n'était pas remplie, pas plus que les conditions permettant de reconnaître l'existence de raisons personnelles majeures au sens de l'alinéa 2 de cette disposition. Le recourant ne pouvait pas davantage se prévaloir de l'art. 8 CEDH en raison de la relation stable qu'il entretenait avec une amie, sans avoir de projet de mariage.
C.
Agissant par la voie du recours en matière de droit public, subsidiairement du recours constitutionnel subsidiaire, X._ conclut, sous suite de frais et dépens, à l'annulation de l'arrêt du Tribunal cantonal du 4 février 2014 et demande au Tribunal fédéral de prolonger son autorisation de séjour.
Le Tribunal cantonal et le Département ont été invités à déposer leur dossier sans échange d'écritures. L'Office fédéral des migrations propose le rejet du recours.
Par ordonnance présidentielle du 11 mars 2014, la demande d'effet suspensif présentée par le recourant a été admise.

Considérant en droit :
1.
1.1. Comme le Tribunal fédéral l'a déjà constaté (arrêt 2C_580/2013 du 20 novembre 2013, consid. 1.1), la vie conjugale du recourant avec une ressortissante suisse ayant cessé d'exister, celui-ci ne peut pas déduire un droit à une autorisation de séjour de l'art. 42 al. 1 LEtr ni de l'art. 49 LEtr. Reste l'art. 50 al. 1 LEtr qui subordonne la prolongation de son autorisation de séjour à certaines conditions dont se prévaut le recourant. En pareilles circonstances, il y a lieu d'admettre un droit de recourir sous l'angle de l'art. 83 let. c ch. 2 LTF, car le point de savoir si les conditions posées par cette disposition sont effectivement réunies en l'espèce relève de l'examen au fond (cf. arrêt 2C_460/2009 du 4 novembre 2009, consid. 2.1.1 non publié aux <ref-ruling>).
1.2. Pour le surplus, l'arrêt attaqué est une décision finale (<ref-law>), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Déposé en temps utile (<ref-law>) et dans les formes requises (<ref-law>) par le destinataire de l'arrêt attaqué qui a qualité pour recourir au sens de l'<ref-law>, le présent recours est donc en principe recevable comme recours en matière de droit public. Partant, le recours constitutionnel subsidiaire (<ref-law>) déposé par le recourant est irrecevable.
1.3. Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral, y compris la violation des droits fondamentaux (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation de l'<ref-law>. En outre, le Tribunal fédéral fonde son raisonnement juridique sur les faits constatés par l'autorité précédente (<ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte ou incomplète - notion qui correspond à celle d'arbitraire (<ref-ruling> consid. 7.1 p. 51) - ou encore en violation du droit au sens de l'<ref-law> (cf. <ref-law>). A cet égard, il faut relever que l'arrêt de renvoi du Tribunal fédéral ne contenait pas de constations de fait ou de motifs contraignants sur les points que le Tribunal cantonal était tenu d'examiner (arrêts 5A_11/2013 du 28 mars 2013, consid. 3.1; 2C_1020/2011 du 16 novembre 2012 et les références citées citées).
1.4. Si le recourant entend s'écarter des constatations de fait de l'autorité précédente (cf. <ref-law>), il doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées. Sinon, il n'est pas possible de tenir compte d'un état de fait divergent de celui qui est contenu dans l'acte attaqué (cf. <ref-ruling>01 consid. 3 p. 104; arrêt 2C_990/2012 du 7 mai 2013 consid. 3.2). En l'espèce, les faits contestés par le recourant, en particulier la durée de la vie commune des époux, se confondent avec l'application et l'interprétation faite par le Tribunal cantonal de l'art. 50 LEtr et doivent être examinés dans ce cadre.
2.
2.1. Selon l'art. 50 al. 1 let. a LEtr, après dissolution de la famille, le droit du conjoint à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 subsiste si l'union conjugale a duré au moins trois ans et l'intégration est réussie. L'existence d'une véritable union conjugale suppose que la relation entre époux soit effectivement vécue et que ces derniers aient la volonté de la maintenir. (<ref-ruling> consid. 2 p. 231; <ref-ruling> consid. 3.1.2 p. 347). Pour cela, il faut se baser essentiellement sur la durée pendant laquelle le couple a fait ménage commun en Suisse (<ref-ruling>13 consid. 3.3.5 p. 120).
2.2. Le Tribunal cantonal a retenu que la première exigence de l'art. 50 al. 1 let. a LEtr n'était pas remplie, puisque les époux s'étaient mariés le 26 octobre 2006 et qu'ils vivaient séparés depuis la fin du mois de septembre 2008. Par ailleurs, le recourant n'était pas parvenu à établir que la communauté familiale avait subsisté, la séparation devant de toute manière être considérée comme définitive au mois de mars 2009.
Contestant cette affirmation, le recourant fait valoir que son mariage a duré plus de trois ans, puisque les époux avaient signé un bail en commun pour la période du 15 septembre 2008 au 30 septembre 2009 et que le Président du Tribunal civil du district de Neuchâtel, dans son ordonnance de mesures protectrices de l'union conjugale du 2 avril 2009, avait constaté que la suspension de la vie commune n'était pas fondée au sens où l'entend l'<ref-law>. Cette constatation n'est toutefois pas de nature à infirmer que toute vie commune des époux avait cessé au mois de mars 2009 au plus tard. En effet, lors de son audience du 31 mars 2009, le Juge civil avait renoncé à la tentative de conciliation, car la séparation devait être considérée comme définitive, l'épouse n'ayant pas l'intention de reprendre la vie commune. Quant à l'ordonnance de mesures protectrices conjugales à laquelle se réfère le recourant, elle constate que les conjoints vivaient désormais séparés et que le domicile conjugal devait être attribué à l'épouse. Il s'ensuit que le recourant ne saurait reprocher au Tribunal cantonal d'avoir procédé à une analyse arbitraire du dossier civil, en retenant que la séparation des époux X._ et Y._ avait été définitive au mois de mars 2009 au plus tard, de sorte que l'art. 50 al. 1 let. a LEtr n'était pas applicable. Il en va de même de l'art. 49 LEtr, dès lors que l'exception à l'exigence du ménage commun suppose que la communauté familiale subsiste, ce qui n'a jamais été le cas en l'espèce, en dépit du bail commun signé en septembre 2008. Les conditions posées par l'art. 50 al. 1 let. a LEtr étant cumulatives (<ref-ruling>13 consid. 3.3.3 p. 119), il n'y pas lieu de vérifier encore si l'intégration est réussie, question que le Tribunal cantonal n'a pas non plus examinée. Reste à déterminer si le recourant peut se prévaloir de raisons personnelles majeures au sens de l'art. 50 al. 1 let. b LEtr pour obtenir une autorisation de séjour sur la base de cette disposition.
2.3. Selon l'art. 50 al. 1 let. b LEtr, après dissolution de la famille, le droit du conjoint et des enfants à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité subsiste si la poursuite du séjour en Suisse s'impose pour des raisons personnelles majeures. L'art. 50 al. 1 let. b et al. 2 LEtr vise à régler les situations qui échappent aux dispositions de l'art. 50 al. 1 let. a LEtr, soit parce que le séjour en Suisse durant le mariage n'a pas duré trois ans ou parce que l'intégration n'est pas suffisamment accomplie ou encore parce que ces deux aspects font défaut mais que - eu égard à l'ensemble des circonstances - l'étranger se trouve dans un cas de rigueur après la dissolution de la famille (ATF <ref-ruling> consid. 3.2.1 p. 348; <ref-ruling> consid. 4.1 p. 7). A cet égard, c'est la situation personnelle de l'intéressé qui est décisive et non l'intérêt public que revêt une politique migratoire restrictive. Par conséquent, il y a lieu uniquement de décider du contenu de la notion juridique indéterminée "raisons personnelles majeures" et de l'appliquer au cas d'espèce, en gardant à l'esprit que l'art. 50 al. 1 let. b LEtr confère un droit à la poursuite du séjour en Suisse, contrairement à l'art. 30 al. 1 let. b LEtr (ATF <ref-ruling> consid. 3.2.1 p. 348; <ref-ruling> consid. 3 et les références citées; arrêt 2C_1062 du 28 mars 2014, consid. 3.2.1). Comme il s'agit de cas de rigueur survenant à la suite de la dissolution de la famille, en relation avec l'autorisation de séjour découlant du mariage, les raisons qui ont conduit à sa dissolution revêtent par conséquent de l'importance. L'admission d'un cas de rigueur personnel survenant après la dissolution de la communauté conjugale suppose que, sur la base des circonstances d'espèce, les conséquences pour la vie privée et familiale de la personne étrangère liées à ses conditions de vie après la perte du droit de séjour découlant de la communauté conjugale (art. 42 al. 1 et 43 al. 1 LEtr) soient d'une intensité considérable (<ref-ruling> consid. 3.1 p. 395; <ref-ruling> consid. 3.2.3 p. 350). La jurisprudence considère aussi que les obstacles à l'exécution du renvoi peuvent, dans certaines circonstances, fonder une raison personnelle majeure au sens de l'art. 50 al. 1 let. b et al. 2 LEtr (cf. ATF <ref-ruling> consid. 3.3.2 p. 351 s.; arrêts 2C_13/2012 du 8 janvier 2013 consid. 3.4; 2C_236/2011 du 2 septembre 2011 consid. 2.2; arrêt précité 2C_1062/2013, consid. 3.2.2).
2.4. Dans l'arrêt attaqué, le Tribunal cantonal retient que l'autorisation obtenue par le recourant à la suite de son mariage est échue depuis le 26 octobre 2009 et que ce dernier n'est ensuite demeuré en Suisse qu'au bénéfice d'une simple tolérance. L'intéressé avait maintenu des contacts intenses et réguliers avec son pays d'origine, dans la mesure où il avait été marié au Kosovo de 1993 à 2004 et avait eu trois enfants de cette union, nés en 1994, 1997 et 2003. Il ne devrait donc pas avoir de difficultés à s'y réinsérer, même s'il y trouvera une situation économique moins favorable qu'en Suisse. Cette constatation n'est pas critiquable, car il faut à cet égard rappeler que, pour reconnaître l'existence d'une "raison personnelle majeure", la question n'est pas de savoir s'il est plus facile pour la personne concernée de vivre en Suisse, mais uniquement d'examiner si, en cas de retour dans le pays d'origine, les conditions de sa réintégration sociale, au regard de sa situation personnelle, professionnelle et familiale, seraient gravement compromises. Or, rien dans les motifs avancés par le recourant ne permet d'aboutir à une telle conclusion. Par ailleurs, s'il s'est bien adapté en Suisse, son intégration socio-professionnelle n'est toutefois pas exceptionnelle et ne suffit pas pour reconnaître l'existence d'une raison personnelle majeure qui empêcherait son retour dans son pays d'origine. Il n'existe ainsi aucun motif personnel grave exigeant la poursuite du séjour en Suisse (<ref-ruling> consid. 3.1 p. 395, 229 consid. 3.1 p. 232 et les références citées). Par conséquent, les premiers juges n'ont pas violé le droit fédéral, ni abusé de leur pouvoir d'appréciation en déniant au recourant le droit d'obtenir une autorisation de séjour sur la base de l'art. 50 al. 1 let. b et al. 2 LEtr.
3.
Le recourant se prévaut encore de l'art. 8 CEDH, en faisant valoir la relation qu'il entretient depuis plus de quatre ans avec son amie travaillant dans le canton de Vaud. Il invoque aussi le fait qu'il vit en Suisse depuis 22 ans, en étant apprécié de son employeur et de ses collègues, ainsi que le fait qu'il n'a jamais recouru à l'aide sociale, ni donné lieu à des plaintes, ce dont le Tribunal cantonal a omis de prendre en considération en ne procédant pas à la pesée des intérêts en présence.
3.1. D'après la jurisprudence, les relations familiales protégées par l'art. 8 § 1 CEDH sont avant tout les rapports entre époux ainsi qu'entre parents et enfants mineurs vivant ensemble (<ref-ruling> consid. 1.3.2 p. 146). Les fiancés ou les concubins ne sont en principe pas habilités à invoquer l'art. 8 CEDH; ainsi, l'étranger fiancé à une personne ayant le droit de s'établir en Suisse ne peut, en règle générale, pas prétendre à une autorisation de séjour, à moins que le couple n'entretienne depuis longtemps des relations étroites et effectivement vécues et qu'il n'existe des indices concrets d'un mariage sérieusement voulu et imminent (cf. arrêt 2C_ 196/2014 du 19 mai 2014, consid. 5.1 et les arrêts cités). Aucun indice concret ne permet en l'espèce de penser que le recourant va se marier avec son amie ayant un droit de présence en Suisse et qu'il fréquente depuis plusieurs années, sans vivre avec elle. L'intéressé ne le prétend d'ailleurs pas, mais soutient que la non-prolongation de son autorisation de séjour entraînerait une séparation du couple qui, compte tenu de son "intégration poussée" violerait son droit à la vie privée garanti par l'art. 8 CEDH.
3.2. Comme l'a relevé le Tribunal cantonal, le recourant ne peut pas se prévaloir du droit au respect de la vie familiale garanti par l'art. 8 CEDH par rapport à sa concubine qu'il ne voit que les week-ends et qu'il n'a pas l'intention d'épouser. Par ailleurs, pour pouvoir déduire un droit à une autorisation de séjour fondée sur le respect de la vie privée prévu à l'art. 8 CEDH, des conditions strictes doivent être remplies, le requérant devant entretenir avec la Suisse des liens sociaux ou professionnels d'une intensité particulière, allant au-delà d'une intégration normale, ce qui n'est pas le cas en l'espèce. Le Tribunal fédéral n'adopte pas une approche schématique qui consisterait à présumer, à partir d'une certaine durée de séjour en Suisse, que l'intéressé y est enraciné et dispose de ce fait d'un droit de présence dans notre pays. En outre, lors de l'application de l'art. 8 CEDH, l'autorité doit procéder à une pesée des intérêts et prendre en considération l'ensemble des circonstances du cas, en considérant la durée du séjour en Suisse comme un élément parmi d'autres (<ref-ruling> consid. 3.2.1 p. 286; arrêts 2C_1111/2013 du 12 mai 2014, consid. 3.4 et 2C_1010/2011 du 31 janvier 2012, consid. 2.4). A cet égard, la Cour cantonale a retenu que les années passées en Suisse devaient être relativisées, dès lors qu'après avoir travaillé comme saisonnier de 1990 à 1998, un délai au 31 mai 2000 lui avait été imparti pour quitter la Suisse à la suite du rejet de sa demande d'asile. Il avait ensuite obtenu une autorisation de séjour en raison de son mariage en octobre 2006, mais avait été au bénéfice d'une simple tolérance depuis l'échéance de celle-ci, le 26 octobre 2009. Les premiers juges n'ont certes pas procédé à cet examen lors de la pesée des intérêts en présence en application de l'art. 8 CEDH, mais ils l'ont fait dans le cadre de l'art. 50 al. 2 LEtr. Sous cet angle, ils ont également constaté que le fait que le recourant ait un travail stable et qu'il soit apprécié de son entourage ne signifiait pas encore qu'il jouisse en Suisse d'une intégration particulière, allant au-delà de ce qui est usuel. Cette argumentation, qui n'est pas différente de celle qui doit être opérée dans le cadre de l'art. 8 CEDH peut être suivie. Elle suffit donc pour rejeter le grief de violation du droit d'être entendu soulevé par le recourant à ce propos. Il s'ensuit que le recourant ne remplit pas les conditions pour obtenir la prolongation de son autorisation de séjour sur la base de l'art. 8 CEDH.
4.
Au vu de ce qui précède, le recours en matière de droit public doit être rejeté, avec suite de frais à la charge du recourant (<ref-law>). Il n'y a pas lieu d'allouer 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.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué à la mandataire du recourant, au Service des migrations, au Département de l'économie et de l'action sociale et au Tribunal cantonal du canton de Neuchâtel, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 4 juillet 2014
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : La Greffière :
Zünd Rochat