Shadowstalkers are demon monsters encountered in various regions in Egypt (Act II). They appear as thick black clouds. When they spot an enemy, they quickly approach it in their cloud-form, thereby being protected against ranged attacks, and then something also black, resembling a some kind of wolfmen, arises from the center of such cloud and attacks in melee. They are melee-fighters of moderate strength, but can be dangerous in numbers.
The first time you'll encounter of of these is usually in the side quest Lowest of the Low, received in Memphis. In order to complete that quest, you will have to fight around 15-20 of these creatures to complete the quest. At this point they can prove to be somewhat difficult enemies.
Later they are occasionally encountered in tombs, along with a group of Eurynomus (also demons) and posing much less of a threat.