Google App Engine - "java.lang.IllegalArgumentException: datastore transaction or write is too large."

it looks like you are hitting the general size limit for puts and delete. you are correct that batch packages and deletes have a 500 object limit, but also a total size limit of roughly 10MB. I'm not sure if this is documented, but I'll check and add them if not.

so try to reduce the number of entities in each delete call.

if you want to dig deeper, the size of a put or delete depends on many factors beyond the size of individual objects, for example. the size of the index rows to be updated. it is also usually based on the delta size of the update itself, rather than the size of existing objects. this means that it is not always intuitive or easy to calculate. these articles can help:

http://code.google.com/appengine/articles/storage_breakdown.html
http://code.google.com/appengine/articles/life_of_write.html