Adaptive mesh refinement and coarsening (AMR) is essential for numerical solution of partial differential equations (PDEs) that describe many multiscale physical problems. Because of the dynamic data structures and large volumes of communication required, the scalability of AMR to thousands of processors has long been considered questionable. We present ALPS, a library for dynamic mesh adaption and redistribution that is designed to scale to tens and hundreds of thousands of cores. Our approach uses parallel octree-based hexahedral finite element meshes and dynamic load balancing based on space filling curves. Our first use of ALPS is to conduct high resolution mantle convection simulations that can resolve thermal boundary layers and faulted plate boundaries, down to 1 km scales. To enable this (local) resolution, we are developing Rhea, a new generation mantle convection code built using the ALPS library. We discuss the design and implementation of ALPS and Rhea along with their parallel performance on Ranger, the 580 Teraflops Teragrid system at TACC.