Delete multiple old diffs in one go.

That doesn't seem like an efficient way to reclaim space. What are the exact sizes of your databases? Are you storing files in it?

We're just using bin/storage dump and just zipping it. Zip file is around 500Mb in size.

Are you storing files in the database or have you configured a different storage engine?

Overall deleting content is something we'd strongly advise against. We'd recommend finding a different solution.

How do I know if files are being stored in the database? What specific database/table should I look at?

The storage engine is mysql. It was configured based on the installation steps.

SELECT table_schema                                        "DB Name", 
   Round(Sum(data_length + index_length) / 1024 / 1024, 1) "DB Size in MB" 
FROM   information_schema.tables 
GROUP  BY table_schema;

Will tell you the size of each table, so you can see what might be causing the most space.

If you're storing all files in MySQL, you may want to move the larger ones to disk (and say, leave files under 32K in MySQL for better performance for avatars). See https://secure.phabricator.com/book/phabricator/article/configuring_file_storage/