There's low storage overhead, but there's definitely a quality control cost. You have to have editors maintaining these pages which (if they are being deleted, generally) are not notable enough to have significant reputable sources devoted to them. As such, you can accumulate subtle vandalism, pranks and biased editing.

There's also a search, navigation and organization cost associated with these sorts of things. They need to be linked together, organized into categories, and if you include a bunch of non-notable garbage it's much harder for people to find the high-quality articles about notable things out there.

"Deletionists" aren't running around deleting things out of spite or something, there are good reasons for the notability guidelines.