We consider the Multi-Period Battery Swapping Station Location Problem (MBSSLP), where the setup costs for battery swapping stations should be minimized while at the same time a certain amount of customer demand should be satisfied. As not every customer is willing to travel to a predestined station, the MBSSLP also considers a certain customer dropout dependent on the length of the detour induced by traveling to an assigned station. In a previous approach, a large neighborhood search was developed for solving MBSSLP instances with up to roughly 2000 potential locations at which battery swapping stations can be placed and 8000 origin-destination (O/D) pairs that describe the trips of customers. However, real world instances can be magnitudes larger. Finding good solutions for such large instances is in general a difficult task, even for metaheuristics, and one often resorts to clustering, refinement, or partitioning approaches that reduce the problem size or decompose it into smaller subproblems. We propose a multilevel optimization (MLO) approach for addressing large scale MBSSLP instances. The basic idea of this approach is to first reduce the problem size by iteratively coarsening an underlying problem represented via a graph until the reduced problem can be solved in reasonable time. Then, a solution for the coarsest problem is generated. Afterwards, a solution to the original problem is obtained by refining the graph, i.e., by iteratively undoing the coarsening, and extending the solution accordingly. Our approach is experimentally evaluated on artificial benchmark scenarios. We evaluate different strategies for coarsening the problem graph and show that our MLO approach can generate reasonable solutions for up to tens of thousands of potential station areas and hundreds of thousands of O/D pairs within one hour.