This is what worked for me, so I am posting this in case it can be useful for somebody else.

1. Collect all branches using command «git branch -a >> BranchNames.txt». Branches are collected in alphabetical order here (this is the way it comes from GIT).
2. Remove from this list «master» and «head» branches.
3. Go to your BitBucket UI, e.g. https://fusion.company.int/stash/projects/AM/repos/your-target-project/branches — branches are displayed in Updated Date order here. Look up and remove from BranchNames.txt all branches you do not want to delete, for example, branches not older than a month. In my case, there were only a few of them. That's why this approach worked for me.
4. Now, when you have all branches that you want to delete, replace in BranchNames.txt:
   
   [remotes/origin/] to [git push origin --delete].
5. Save the resulted file as a .cmd file (in my case I have Windows machine) and run it from your git project folder location. It takes some time to run all batch commands but I was not in a hurry and it worked for me.