Statistical modeling of a nonstationary spatial extremal dependence structure is a challenging problem. In practice, parametric max-stable processes are commonly used for modeling spatially-indexed block maxima data, where the stationarity assumption is often made to make inference easier. However, this assumption is unreliable for data observed over a large or complex domain. In this work, we develop a computationally-efficient method to estimate nonstationary extremal dependence using max-stable processes, which builds upon and extends an approach recently proposed in the classical geostatistical literature. More precisely, we divide the spatial domain into a fine grid of subregions, each having its own set of dependence-related parameters, and then impose LASSO ($L_1$) or Ridge ($L_2$) penalties to obtain spatially-smooth estimates. We then also subsequently merge the subregions sequentially together with a new algorithm to enhance the model's performance. Here we focus on the popular Brown-Resnick process, although extensions to other classes of max-stable processes are also possible. We discuss practical strategies for adequately defining the subregions and merging them back together. To make our method suitable for high-dimensional datasets, we exploit a pairwise likelihood approach and discuss the choice of pairs to achieve reasonable computational and statistical efficiency. We apply our proposed method to a dataset of annual maximum temperature in Nepal and show that our approach fits reasonably and realistically captures the complex non-stationarity in the extremal dependence.