Try going to the place where you bought, got or stolen your current horse. Shadowmere should be nearby. Try casting the Alteration spell, Detect Life, or use the Aura Whisper dragon shout (longer range than Detect Life) to try to find Shadowmere. Shadowmere should be within the range of Detect Life or Aura Whisper.
If not, Shadowmere might have gone back to the place where you first got him: the pool in front of the Dark Brotherhood sanctuary entrance, in Falkreath Hold (near Falkreath, the city).
If you still can't find Shadowmere, try teleporting him to your current location by using console commands (make sure you are outside [a location you can Fast Travel away from] and not in a walled city when doing this, as horses are not meant to go inside walled cities or other indoor locations, and may cause glitches).
Console commands to teleport Shadowmere to the player's current location:
'prid' targets an entity - Shadowmere in this case. '9CCD8' is Shadowmere's RefID. 'moveto player' moves that targetted entity near the vicinity of the player.
If Shadowmere is still not near your vicinity after doing this, he may be dead (that or his corpse was teleported near you). Try these commands to bring him back in the game and resurrect him:
More info on console commands here: http://uesp.net/wiki/Skyrim:Console