In RSE, the Move Deleter can be found in Lilycove, east of the Department Store.
In FRLG, the Move Deleter is located in Fuschia City, right next to the Pokemon Center.
Since HM moves cannot be deleted by the trainer, it is doubly important that you DO NOT teach your regular team Pokes any of them, with the lone exception of Surf. What you need to do instead is to have a crappy Poke be your HM slave and slap all the HM moves on it. That way you don't run into this problem. In RSE, the best HM slaves are Tropius and Wailmer. Each one has the capacity to learn 5 of the HM moves. At least they are useful in some way.