When I'm at my Home page I swipe from left to right, and in the resulting screen tap on the weather icon in the middle task bar. To add a location I'll type in a city in the search box at the top and then at the bottom there's an 'Add' button; to delete a city, tap on that search box to show the listing of saved cities, and long-press to delete unwanted ones.
Not the most elegant user interface but at least that's what works with my phone (running Nougat using the default weather app). If this similar to what you've already tried to do, is this not working or what else have you tried?