Scorpions are common in the desert areas, where they are by far the most dominant creature of the most northerly Tulimshar desert and beach area (when considered alongside their other cousins). But these creatures have wandered far and wide, and can be found in the Woodland forest areas, and in swamps. They have even found their way into some of the caves.
Killing these creatures, you will establish yourself a good reputation with Sagatha if you've by chance got on her bad side by killing her beloved creatures.
If you are still on the Island of Candor, and can't find the Scorpion there that Valon asks for, you will get one by doing the Hasan part of the quest. It is not necessary to leave the island to finish these quests.