Declaring Targets happens before paying costs. So, yes. You annouce Wasteland, you declare target (in this case wasteland), then you pay costs (in this case tap and sacrifice). Then the ability goes on the stack. And when it comes time to resolve, it is countered for having no legal targets.
For a more recent example of the same concept, look into Ghost Quarter
5/1/2006: If you target Ghost Quarter with its own ability, the ability will be countered because its target is no longer in play. You won't get to search for a land card.