The short answer is, just delete the file(s), there's not really an uninstall process.
The longer answer is: The makefile that was used to build mplayer/mencoder has an "uninstall" target. To "officially" uninstall, use the same makefile that was used to compile mplayer & do a "make uninstall". That will do the following:
rm -f $(BINDIR)/mplayer$(EXESUF) $(BINDIR)/gmplayer$(EXESUF)
rm -f $(BINDIR)/mencoder$(EXESUF)
rm -f $(MANDIR)/man1/mencoder.1 $(MANDIR)/man1/mplayer.1
rm -f $(prefix)/share/pixmaps/mplayer.xpm
rm -f $(prefix)/share/applications/mplayer.desktop
rm -f $(MANDIR)/man1/mplayer.1 $(MANDIR)/man1/mencoder.1
rm -f $(foreach lang,$(MAN_LANG),$(foreach man,mplayer.1 mencoder.1,$(MANDIR)/$(lang)/man1/$(man)))
If you don't have that makefile, then use the above as a guide. Again, all that is NOT necessary & doing all of it will likely make no difference in your attempts to make mencoder work.
FWIW, the "configure" step of mplayer is very important (that's the "configure" in "configure; make; make install")... look at what it spits out & correct everything that gives a 'no' answer. You'll likely find that all your mencoder problems are related to the fact that the correct libs are not available at compile time. mplayer will compile and run just fine without the correct libs for encoding & it doesn't do a good job of letting the user know that it won't be creating the encoder.