Faits:
A.
Par ordonnance du 4 février 2013, le Ministère public de la République et canton de Genève a classé la plainte déposée par X._ le 1er décembre 2009 pour escroquerie, banqueroute frauduleuse et diminution effective de l'actif au bénéfice des créanciers, formellement dirigée contre inconnu, mais qui visait les sociétés B._ Inc., ayant son siège au Canada, C._ SA, ayant son siège à Genève, et A._, qui est notamment administrateur de cette dernière. Il leur reprochait essentiellement, en substance, de lui avoir fait croire que les ressources de la société étaient suffisantes pour que son salaire lui soit versé, ce qui était faux. Il avait été induit en erreur pour qu'il continue son activité, ce qui constituait une escroquerie puisqu'il n'avait finalement perçu aucune rémunération pour les mois de mars à juin 2009.
B.
Par arrêt du 4 avril 2013, la Chambre pénale de recours de la Cour de justice de Genève a rejeté le recours formé par X._ en tant qu'il portait sur la prévention d'escroquerie et l'a admis en relation avec les infractions contre la faillite, renvoyant le dossier au Ministère public sur ce point. Elle a laissé les frais de la procédure de recours à la charge de l'Etat et alloué à X._ une indemnité de 1'500 francs.
C.
X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut à son annulation en tant qu'il ne retient pas une prévention d'escroquerie et lui alloue une indemnité de 1'500 francs, qu'il juge trop faible.

Considérant en droit:
1.
Le Tribunal fédéral contrôle librement la recevabilité des recours qui sont déposés devant lui (<ref-ruling> consid. 1 p. 369; <ref-ruling> consid. 1 p. 472).
1.1. Selon l'art. 81 al. 1 let. a et b ch. 5 LTF, la partie plaignante qui a participé à la procédure de dernière instance cantonale est habilitée à recourir au Tribunal fédéral si la décision attaquée peut avoir des effets sur le jugement de ses prétentions civiles. Constituent de telles prétentions celles qui sont fondées sur le droit civil et doivent en conséquence être déduites ordinairement devant les tribunaux civils. Il s'agit principalement des prétentions en réparation du dommage et du tort moral au sens des <ref-law>.
Selon l'<ref-law>, il incombe notamment au recourant d'alléguer les faits qu'il considère comme propres à fonder sa qualité pour recourir (cf. <ref-ruling> consid. 1 p. 356, 249 consid. 1.1 p. 251). Lorsque, comme en l'espèce, le recours est dirigé contre une décision de classement, il n'est pas nécessaire que la partie plaignante ait déjà pris des conclusions civiles (<ref-ruling> consid. 1.3.1 p. 248). En revanche, elle doit expliquer dans son mémoire quelles prétentions civiles elle entend faire valoir contre l'intimé. Comme il n'appartient pas à la partie plaignante de se substituer au Ministère public ou d'assouvir une soif de vengeance, la jurisprudence entend se montrer restrictive et stricte, et le Tribunal fédéral n'entre en matière que s'il ressort de façon suffisamment précise de la motivation du recours que les conditions précitées sont réalisées, à moins que, compte tenu notamment de la nature de l'infraction alléguée, l'on puisse le déduire directement et sans ambiguïté (<ref-ruling> consid. 2.4 p. 222 s.; <ref-ruling> consid. 1a p. 187; <ref-ruling> consid. 1 p. 141; <ref-ruling> consid. I/4a p. 52 s.).
1.2. Le recourant indique que l'admission de sa plainte du chef d'escroquerie aura "de toute évidence" une incidence sur le jugement de ses prétentions civiles", sans fournir d'autres explications à cet égard.
Une telle affirmation ne permet pas encore de savoir quelles prétentions le recourant entend invoquer et elle est à cet égard insuffisante pour fonder sa qualité pour recourir. A._, qui était la seule partie intimée devant la Chambre pénale de recours de la Cour de justice, n'est pas personnellement débiteur des prétentions découlant du contrat de travail conclu par le recourant avec C._ SA, voire B._ Inc. et la seule action civile formée par le recourant à ce jour l'a d'ailleurs été devant la juridiction des prud'hommes, à l'encontre de ces sociétés. Le recourant n'a par ailleurs pas invoqué qu'il serait en mesure de faire valoir des prétentions directement à l'encontre de A._, eu égard à sa qualité d'administrateur de C._ SA. La recevabilité du recours au regard de l'art. 81 al. 1 let. a et b ch. 5 LTF, en tant qu'il porte sur le fond, est dès lors douteuse. Cette question n'a cependant pas besoin d'être tranchée pour les motifs qui suivent.
2.
Le recourant invoque que la décision cantonale n'est pas suffisamment motivée dans la mesure où elle n'explique pas en quoi, au vu du lien de confiance qui l'unissait à la société qui l'employait, le comportement de A._ n'était pas astucieux.
2.1. L'obligation de l'autorité de motiver sa décision découle du droit d'être entendu garanti par l'art. 29 al. 2 Cst. Selon la jurisprudence, il suffit que le juge mentionne, au moins brièvement, les motifs qui l'ont guidé et sur lesquels il a fondé sa décision, de manière à ce que l'intéressé puisse se rendre compte de la portée de celle-ci et l'attaquer en connaissance de cause. L'autorité n'a pas l'obligation d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties, mais elle peut au contraire se limiter à ceux qui lui paraissent pertinents (<ref-ruling> consid. 5.1 p. 237 et les arrêts cités).
2.2. Selon la cour cantonale, le fait pour un employé de réclamer son salaire à un employeur qui ne le verse finalement pas n'est pas à lui seul pénalement relevant. La composante pénale de la tromperie astucieuse ne ressortait d'aucun élément tangible. En effet, rien n'indiquait que le recourant avait été induit à croire que la situation de la société allait s'améliorer et que les problèmes financiers rencontrés allaient brutalement disparaître, autorisant par là un paiement de son salaire. Bien au contraire, le refus de C._ SA de continuer à prêter de l'argent sans garantie de profitabilité avait été expressément mentionné par A._. De plus, les reproches clairement formulés par ce dernier contre l'activité, selon lui désastreuse, du recourant ne pouvait raisonnablement être comprise comme une volonté de maintenir à tout prix le recourant à son poste. Ainsi, toute personne raisonnable placée dans la situation du recourant aurait compris que la situation, critique, de la société et les reproches formulés par celui qu'il considérait comme son supérieur hiérarchique ne constituaient pas une tromperie, encore moins astucieuse, pour le pousser à fournir son travail afin de, volontairement, le priver de tout salaire. Les nombreux indicateurs, volontairement ou involontairement, donnés par A._ étaient, bien plutôt, autant d'avertissements clairs de ce qui allait se passer. Dans ce cadre, aucun élément concret ne permettait de concevoir que A._ avait l'intention, même par dol éventuel, de ne pas payer le recourant.
Il apparaît dès lors que la motivation de l'autorité précédente était suffisante pour permettre au recourant de comprendre la décision cantonale et la contester, comme le démontre d'ailleurs ses écritures devant la cour de céans. Le grief qu'il soulève quant à la prétendue motivation insuffisante de la décision attaquée doit être rejeté dans la mesure où il est recevable.
3.
Le recourant conteste la décision cantonale en tant qu'elle a considéré que l'infraction d'escroquerie n'était pas réalisée. Il fait ainsi, implicitement, valoir une violation des règles relatives au classement des procédures pénales (<ref-law>).
3.1. Selon l'<ref-law> (RS 312.0), le Ministère public ordonne le classement de tout ou partie de la procédure lorsqu'aucun soupçon justifiant une mise en accusation n'est établi (let. a), lorsque les éléments constitutifs d'une infraction ne sont pas réunis (let. b), lorsque des faits justificatifs empêchent de retenir une infraction contre le prévenu (let. c), lorsqu'il est établi que certaines conditions à l'ouverture de l'action pénale ne peuvent pas être remplies ou que des empêchements de procéder sont apparus (let. d) ou lorsqu'on peut renoncer à toute poursuite ou à toute sanction en vertu de dispositions légales (let. e). L'<ref-law> prévoit encore deux autres motifs de classement exceptionnels (intérêt de la victime ou consentement de celle-ci).
Selon la jurisprudence, cette disposition doit être appliquée conformément à l'adage in dubio pro duriore. Celui-ci découle du principe de la légalité (art. 5 al. 1 Cst. et 2 al. 2 CPP en relation avec les art. 319 al. 1 et 324 CPP; <ref-ruling> consid. 4.2 p. 91) et signifie qu'en principe, un classement ou une non-entrée en matière ne peuvent être prononcés par le ministère public que lorsqu'il apparaît clairement que les faits ne sont pas punissables ou que les conditions à la poursuite pénale ne sont pas remplies. Le ministère public et l'autorité de recours disposent, dans ce cadre, d'un pouvoir d'appréciation que le Tribunal fédéral revoit avec retenue. La procédure doit se poursuivre lorsqu'une condamnation apparaît plus vraisemblable qu'un acquittement ou lorsque les probabilités d'acquittement et de condamnation apparaissent équivalentes, en particulier en présence d'une infraction grave (<ref-ruling> consid. 4.1.2 p. 91; 186 consid. 4.1 p. 190; <ref-ruling> consid. 2.5 p. 288).
3.2. Par son argumentation, le recourant critique la décision cantonale en tant qu'elle a considéré que A._ ne l'avait pas trompé de manière astucieuse. Il ne démontre en revanche pas que celui-ci avait l'intention de ne pas le payer, comme l'a constaté la cour cantonale. Il relève que A._ lui aurait demandé de demeurer à son poste ou lui aurait laissé entendre que des paiements interviendraient prochainement, des solutions avantageuses pour les employés étant négociées. Ces circonstances ne sont cependant pas propres à établir l'intention de A._ de porter préjudice au recourant et de se procurer un enrichissement illégitime. Le recourant relève, au contraire, que A._ voulait maintenir la structure de C._ SA afin de trouver un nouvel actionnaire ou un repreneur auquel il aurait cédé la société. Cela tend à démontrer que les agissements de l'intéressé n'étaient pas destinés à amener le recourant à accomplir un acte préjudiciable à ses intérêts pécuniaires, mais visaient à maintenir la structure en activité. L'escroquerie est une infraction intentionnelle, l'intention devant porter sur tous les éléments constitutifs de l'infraction (<ref-ruling> consid. 5.3 p. 213 s.). Ainsi, même s'il fallait admettre, d'un point de vue objectif, que A._ a astucieusement trompé le recourant, comme celui-ci le soutient, la condition subjective de l'infraction ne serait, en tout état de cause, pas remplie. Il ne se justifie dès lors pas d'examiner davantage l'argumentation du recourant quant au caractère prétendument astucieux de la tromperie dont il aurait été victime. En confirmant le classement, faute de réalisation des conditions de l'infraction d'escroquerie, la cour cantonale n'a pas violé le droit fédéral. Le grief doit être rejeté.
4.
Le recourant conteste le montant des dépens d'appel qui lui ont été alloués par la cour cantonale.
4.1. Il reproche en premier lieu à celle-ci d'avoir considéré qu'il n'avait pas produit une note détaillées des activités de son conseil. Si tel était le cas, il lui appartenait toutefois de solliciter des renseignements supplémentaires, sauf à violer son droit d'être entendu.
La simple indication du recourant selon laquelle il déclare invoquer formellement une violation de son droit d'être entendu ne répond pas, en tant que telle, aux exigences de l'<ref-law>, selon lesquelles un tel grief doit être exposé de façon claire et détaillée par le recourant (principe d'allégation; <ref-ruling> consid. 1.4). Il est irrecevable. Au demeurant, aucune violation de son droit d'être entendu ne saurait être retenue dans la mesure où il a pu faire valoir le montant qu'il réclamait avant que la cour cantonale ne prenne une décision sur les dépens et qu'il lui appartenait, en vertu de l'<ref-law>, de chiffrer et justifier ses prétentions, faute de quoi l'autorité pénale n'entre pas en matière sur la demande, la maxime de l'instruction n'étant pas applicable en la matière (Wehrenberg/Bernhard, in Basler Kommentar, Schweizerische Strafprozessordnung, 2011, n° 12 ad <ref-law>).
4.2. Le recourant persiste à réclamer le montant total qu'il demandait devant l'autorité cantonale pour les heures de travail de son conseil, soit 7'500 francs, ce qui représente selon lui une quinzaine d'heures.
Il ne critique toutefois pas la décision attaquée en tant qu'elle retient qu'en raison de l'admission partielle du recours, seul un montant restreint pouvait lui être accordé à titre de dépens. Il est rappelé à cet égard que selon l'<ref-law>, la partie plaignante peut demander au prévenu une juste indemnité pour les dépenses obligatoires occasionnées par la procédure lorsqu'elle obtient gain de cause. Tel n'est toutefois pas le cas en l'espèce en tant que le recours portait sur l'infraction d'escroquerie et sur le grief de violation du droit d'être entendu en raison d'un prétendu défaut de motivation puisqu'il a été rejeté sur ces deux points. Le recourant ne pouvait donc obtenir de dépens à cet égard et il était conforme au droit fédéral, pour ce motif déjà, de ne pas allouer l'entier du montant réclamé.
Pour le surplus, le recourant n'explique pas en quoi, au vu de ce qui précède, le montant de 1'500 francs serait trop faible, se bornant à affirmer qu'il est évident qu'il est largement insuffisant. Il laisse entendre que la prétendue faiblesse du montant alloué résulterait d'une inimitié de la cour cantonale à l'encontre de son conseil, comme cela ressortirait des commentaires peu adéquats de celle-ci. Il ne ressort cependant d'aucune manière des termes de la décision attaquée que les magistrats cantonaux auraient nourri une quelconque animosité à l'encontre du conseil du recourant. Le grief doit être rejeté dans la mesure où il est recevable.
5.
Le recours doit être rejeté dans la mesure où il est recevable. Le recourant, qui succombe, supporte les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 4'000 francs, sont mis à la charge du recourant.
3.
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 27 août 2013
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
Le Greffier: Rieben