Have you tried logging into your OneDrive account via a browser on your computer?
OneDrive has some weird functionalities whereby if you delete a folder on OneDrive it just deletes it locally and doesn't sync with the cloud. Try logging into OneDrive via office.com and then check your recycling bin there