Did Settings > General > iPhone Storage > Review Large Attachments not work?
However, deleting through this interface would be a pain. You select "Edit" and then each attachment is selected individually.
Really wish there was a "delete all" or "select all".