Faits :
A.
Le 18 novembre 2021, A._, ressortissant tunisien né en 1977, a été interpellé à la gare de Neuchâtel par le corps des gardes-frontière Douane Mittelland alors qu'il ne disposait d'aucun titre de séjour valable en Suisse. Auditionné le même jour par les autorités compétentes, l'intéressé a déclaré vivre à Neuchâtel chez son amie B._, avec laquelle il avait l'intention de se marier (cf. <ref-law>).
Le 18 novembre 2021, l'Administration fédérale des douanes (devenue entretemps l'Office fédéral de la douane et de la sécurité des frontières; ci-après: l'Office fédéral) a prononcé le renvoi de Suisse de A._ (cf. <ref-law>).
B.
Par décision du 6 décembre 2021, le Département de l'emploi et de la cohésion sociale du canton de Neuchâtel (ci-après: le Département) a refusé de restituer l'effet suspensif au recours déposé par A._ contre la décision de renvoi susmentionnée.
Le 22 décembre 2021, la Cour de droit public du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal) a déclaré irrecevable pour cause de tardiveté le recours formé par A._ contre la décision du Département du 6 décembre 2021.
C.
A l'encontre de la décision du 22 décembre 2021, A._ dépose un recours constitutionnel subsidiaire auprès du Tribunal fédéral. Il conclut, sous suite de frais et dépens, à l'annulation de la décision entreprise et à la restitution de l'effet suspensif "aux recours du 24 novembre 2021 et du 15 décembre 2021".
Le Département, le Service des migrations et le Tribunal cantonal concluent au rejet du recours. Le Secrétariat d'Etat aux migrations ne s'est pas déterminé.
Par ordonnance du 27 janvier 2022, la Présidente de la IIe Cour de droit public du Tribunal fédéral a accordé l'effet suspensif au recours.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>) et contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1).
1.1. La décision rendue le 6 décembre 2021 par le Département, qui refuse de restituer l'effet suspensif au recours formé par l'intéressé à l'encontre d'une décision de renvoi, est une décision incidente (cf. arrêt 2C_990/2017 du 6 août 2018 consid. 1.2). La décision d'irrecevabilité du 22 décembre 2021 met fin à la procédure devant le Tribunal cantonal; néanmoins, du moment que le recours à l'origine de ce prononcé était dirigé contre une décision incidente, la décision entreprise revêt elle aussi le caractère d'une décision incidente (arrêts 2C_1156/2018 du 12 juillet 2019 consid. 1.1; 2C_1155/2016 du 3 avril 2017 consid. 1.2).
La voie de recours contre une telle décision est déterminée par le litige principal (cf. <ref-ruling> consid. 1.4; arrêts 2C_610/2020 du 19 novembre 2020 consid. 1.3; 2C_990/2017 du 6 août 2018 consid. 1.2; 2C_244/2017 du 19 avril 2017 consid. 1.2), lequel concerne le renvoi de Suisse du recourant. Aux termes de l'art. 83 let. c ch. 4 LTF, le recours en matière de droit public est irrecevable notamment contre les décisions en matière de droit des étrangers qui concernent le renvoi. Le recours en matière de droit public étant ainsi en l'espèce exclu en vertu de cette disposition, c'est à juste titre que le recourant a formé un recours constitutionnel subsidiaire (<ref-law>; cf. arrêt 2D_9/2017 du 3 octobre 2017 consid. 1.3).
1.2. A qualité pour former un recours constitutionnel subsidiaire quiconque a pris part à la procédure devant l'autorité précédente ou a été privé de la possibilité de le faire (<ref-law>) et a un intérêt juridique à l'annulation ou à la modification de la décision attaquée (<ref-law>). Indépendamment de sa qualité pour recourir sur le fond, le destinataire d'un arrêt cantonal d'irrecevabilité a qualité pour contester ce prononcé sous l'angle de l'<ref-law> en invoquant une violation de ses droits de partie à la procédure (arrêt 1D_10/2011 du 14 novembre 2011 consid. 1.3). Tel est le cas en l'espèce, le recourant reprochant au Tribunal cantonal de ne pas avoir statué sur son recours et d'avoir ainsi commis un déni de justice formel (art. 29 al. 1 Cst.).
1.3. En vertu de l'<ref-law> (applicable par renvoi de l'<ref-law>), les décisions incidentes notifiées séparément qui ne portent pas sur la compétence ou sur une demande de récusation ne peuvent faire l'objet d'un recours constitutionnel subsidiaire que si elles peuvent causer un préjudice irréparable (let. a), ou si l'admission du recours peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse (let. b). A moins que ces conditions ne sautent aux yeux, il appartient au recourant d'en démontrer la réalisation sous peine d'irrecevabilité (<ref-ruling> consid. 2.5). S'agissant en particulier du préjudice irréparable exigé par l'<ref-law>, le refus d'accorder l'effet suspensif à un recours contre une décision de renvoi n'est en principe susceptible de causer un tel préjudice que lorsque la personne concernée allègue de manière défendable un droit à une autorisation de séjour (cf. arrêt 2D_33/2021 du 30 septembre 2021 consid. 5.3 et la jurisprudence citée).
En l'occurrence, la décision entreprise, qui déclare irrecevable le recours formé par l'intéressé contre la décision du Département du 6 décembre 2021 refusant de suspendre l'exécution de son renvoi de Suisse, est susceptible de causer un préjudice irréparable au recourant, dans la mesure où celui-ci - qui n'est au demeurant pas assisté par un avocat - invoque (au fond) de manière défendable un droit à demeurer en Suisse en vue de se marier (cf. recours, p. 4; art. 14 Cst. et 12 CEDH; cf. arrêt 2C_990/2017 du 6 août 2018 consid. 1.4). Le recours est donc recevable sous l'angle des art. 117 et 93 al. 1 let. a LTF.
1.4. Pour le surplus, le recours, dirigé contre une décision rendue en dernière instance cantonale par une autorité judiciaire supérieure (art. 114 et 86 al. 1 let. d et al. 2 LTF), a été déposé en temps utile (art. 117 et 100 al. 1 LTF) et dans les formes requises (<ref-law>). Il est donc recevable, sous réserve de ce qui suit.
1.5. Les conclusions sur le fond ne sont en principe pas admissibles contre une décision d'irrecevabilité (arrêts 2C_1156/2018 du 12 juillet 2019 consid. 1.4; 2D_11/2018 du 12 juin 2018 consid. 1.3; 2C_821/2017 du 23 mars 2018 consid. 1.3). La conclusion tendant à la restitution de l'effet suspensif "aux recours du 24 novembre 2021 et du 15 décembre 2021" est dès lors irrecevable, puisqu'elle concerne le fond du litige porté devant le Tribunal cantonal.
En sus de cette conclusion irrecevable, le recourant conclut uniquement à l'annulation de la décision attaquée. Des conclusions purement cassatoires ne sont en principe pas suffisantes (art. 117 et 107 al. 2 LTF; arrêt 2C_406/2020 du 10 février 2021 consid. 2.4). Dès lors que l'on comprend, à la lecture du mémoire, que l'intéressé critique le fait que l'autorité précédente ne soit pas entrée en matière sur son recours et exige en définitive que celle-ci le fasse, il convient de ne pas se montrer trop formaliste et d'entrer en matière sur le recours (cf. <ref-ruling> consid. 1.3; arrêt 2C_284/2016 du 20 janvier 2017 consid. 1.3, non publié in <ref-ruling>).
2.
Le recours constitutionnel subsidiaire ne peut être formé que pour violation des droits constitutionnels (<ref-law>). En vertu de l'<ref-law>, applicable par renvoi de l'<ref-law>, les griefs y relatifs doivent être invoqués et motivés par le recourant, à savoir expressément soulevés et exposés de manière claire et détaillée, en précisant en quoi consiste la violation (cf. <ref-ruling> consid. 5.1; <ref-ruling> consid. 2.1).
3.
Le recourant invoque une application arbitraire de l'art. 64 al. 3 de la loi fédérale du 16 décembre 2005 sur les étrangers et l'intégration (LEI; RS 142.20).
3.1. Une décision est arbitraire (art. 9 Cst.) lorsqu'elle contredit clairement la situation de fait, qu'elle viole gravement une norme ou un principe juridique clair et indiscuté ou qu'elle heurte d'une manière choquante le sentiment de la justice et de l'équité. Il n'y a pas arbitraire du seul fait qu'une solution autre que celle de l'autorité précédente semble concevable, voire préférable. Pour qu'une décision soit annulée pour cause d'arbitraire, il ne suffit pas que sa motivation soit insoutenable; il faut encore que cette décision soit arbitraire dans son résultat (<ref-ruling> consid. 5.4).
3.2. L'art. 64 LEI prévoit ce qui suit:
" Art. 64 - Décision de renvoi
1. Les autorités compétentes rendent une décision de renvoi ordinaire à l'encontre:
a. d'un étranger qui n'a pas d'autorisation alors qu'il y est tenu;
b. d'un étranger qui ne remplit pas ou ne remplit plus les conditions d'entrée en Suisse (art. 5);
[...]
3. La décision visée à l'al. 1, let. a et b, peut faire l'objet d'un recours dans les cinq jours ouvrables suivant sa notification. Le recours n'a pas d'effet suspensif. L'autorité de recours statue dans les dix jours sur la restitution de l'effet suspensif. "
3.3. Le Tribunal cantonal a constaté que la décision du Département du 6 décembre 2021 avait été notifiée au mandataire du recourant le 8 décembre 2021. Cette autorité a ainsi considéré, se fondant sur l'art. 64 al. 3 LEI, que le délai de recours de 5 jours prévu par cette disposition avait commencé à courir le 9 décembre 2021 et était arrivé à échéance le 13 décembre 2021. Le recours de l'intéressé, interjeté le 15 décembre 2021, était dès lors tardif.
3.4. L'art. 64 al. 3 LEI prévoit clairement que la décision de renvoi rendue par l'autorité compétente doit être contestée dans un délai de "cinq jours ouvrables". En revanche, il ne ressort pas sans équivoque du texte de la loi que ce délai s'applique aussi au recours interjeté auprès de la (deuxième) instance cantonale de recours (en l'occurrence le Tribunal cantonal). Dans un arrêt récent, le Tribunal fédéral a laissé la question ouverte, considérant que, du moment que la décision rendue par la (première) instance cantonale de recours n'indiquait pas un délai de cinq jours et que l'application de ce délai au recours interjeté auprès du Tribunal cantonal administratif ne résultait pas clairement de l'art. 64 al. 3 LEI, la partie recourante pouvait de bonne foi se prévaloir d'un délai plus long (arrêt 2D_9/2017 du 3 octobre 2017 consid. 3.2 et 3.3).
La question souffre - ici aussi - de demeurer indécise. En effet, que l'on soumette le recours déposé auprès du Tribunal cantonal au délai prévu par l'art. 64 al. 3 LEI (5 jours ouvrables), ou au délai applicable dans le canton de Neuchâtel aux recours contre une décision incidente en matière administrative (10 jours; cf. art. 34 al. 3 de la loi neuchâteloise sur la procédure et la juridiction administratives [LPJA/NE; RS/NE 152.130]), force est de constater que celui-ci aurait de toute manière été déposé à temps. Comme l'a relevé l'autorité précédente, le délai de recours a commencé à courir le 9 décembre 2021. Il serait donc arrivé à échéance - à supposer qu'il ait été de cinq jours - le 15 décembre 2021 en application de l'art. 64 al. 3 LEI (le samedi 11 décembre et le dimanche 12 décembre n'étant pas des jours ouvrables), respectivement quelques jours plus tard en application de l'art. 34 al. 3 LPJA/NE. Interjeté le 15 décembre 2021, le recours était donc dans tous les cas recevable sous cet angle. Dès lors, en considérant que tel n'était pas le cas, le Tribunal cantonal a appliqué arbitrairement le droit fédéral ou le droit cantonal. Le grief de l'intéressé à ce sujet est bien fondé.
4.
Il découle de ce qui précède que le recours doit être admis dans la mesure où il est recevable, la décision entreprise annulée et la cause renvoyée au Tribunal cantonal pour qu'il entre en matière sur le recours déposé le 15 décembre 2021 par l'intéressé.
Compte tenu de l'issue du litige, il ne sera pas perçu de frais judiciaires (art. 66 al. 1 et 4 LTF). Ayant obtenu gain de cause avec l'aide d'un mandataire professionnel, le recourant a droit à des dépens (art. 68 al. 1 et 2 LTF), à charge du canton de Neuchâtel.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis dans la mesure où il est recevable.
2.
La décision du 22 décembre 2021 est annulée et la cause est renvoyée au Tribunal cantonal pour qu'il entre en matière sur le recours déposé le 15 décembre 2021 par l'intéressé.
3.
Il n'est pas perçu de frais judiciaires.
4.
Le canton de Neuchâtel versera au recourant une indemnité de 2'000 fr. à titre de dépens.
5.
Le présent arrêt est communiqué au mandataire du recourant, au Service des migrations et au Département de l'emploi et de la cohésion sociale du canton de Neuchâtel, au Tribunal cantonal du canton de Neuchâtel, Cour de droit public, à l'Office fédéral de la douane et de la sécurité des frontières, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 19 avril 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. Ermotti