We study the interatomic exchange interactions and Curie temperatures in half-metallic semi-Heusler compounds NiCrZ (Z=p, Se, Te) and NiVAs. The study is performed within the framework of density functional theory. The calculation of exchange parameters is based on the frozen-magnon approach. It is shown that the exchange interactions in NiCrZ vary strongly depending on the Z constituent. The Curie temperature is calculated within mean field and random phase approximations. The difference between two estimated values is related to the properties of the exchange interactions. The predicted Curie temepratures of all four systems are considerably above room temperature. The relation between half-metallicity and the value of the Curie temperature is discussed. The combination of a high spin polarization of charge carriers and a high Curie temperature makes these Heusler alloys interesting candidates for spintronics applications.