Covering problems constitute an important family of facility location problems. This paper intro- duces a new exact algorithm for two important members of this family: i) the maximal covering location problem, which requires finding a subset of facilities that maximizes the amount of demand covered while respecting a budget constraint on the cost of the facilities; and ii) the partial set covering location problem, which minimizes the cost of the open facilities while forcing a certain amount of demand to be covered. We study an effective decomposition approach to the two problems based on the branch-and-Benders-cut reformulation. We also report the results of a series of computational experiments demonstrating that, thanks to this decomposition techniques, optimal solutions can be found very quickly, even for benchmark instances involving up to twenty million demand points.