I had success with rmrec. It removed a bunch of packages that were not depended on by my other packages. Whereas brew autoremove did not help me.

pkgname is the name of the original pkg which you had attempted to install.

brew tap ggpeti/rmrec
brew rmrec pkgname

That removed some of the unneeded formula. I still had to do a manual scan at the top level, though.