Google has a reputation for efficiency, but their appengine datastore must be the least efficient piece of code I've ever come across. Deleting 10,000 entities took 1,027 cpu seconds (17 cpu minutes). Each entity is 4 write operations (only one indexed property). (I used delete_async on batches of 1,000 at a time.)
It is way more expensive to do the deletion than additions of the same data which really makes no sense.