The mobility performance of off-road vehicles involves the interaction between the vehicle tires and soil that requires more advanced and robust simulation methods to accurately model . The finite element method (FEM)  can be a good approach to compute deformations of the tire and soil, but analytical constitutive models of soil used in FEM typically lack accuracy, for example in problems involving large deformations. Discrete element method (DEM)  is a more accurate approach to capture the soil constitutive features, but for the simulations of a large ground vehicle traversing over deformable terrain, the current DEM methods require modeling of soil particles at a size too large to be real, and the simulation times are prohibitively large. It is proposed in this work to develop a multi-scale FEM-DEM deformable terrain model for physics-based off-road mobility simulation to facilitate a cross-scale understanding of granular material behavior that benefits from the strengths of both FEM and DEM methods. In this article, a hierarchical multi-scale (HMS) computational framework is used to develop a hybrid parallel computational model for off-road mobility tire-soil interaction problems on high performance computer (HPC) systems. The HMS computational multi-scale framework for scale-bridging was first proposed and developed by Knap et al  at CCDC US Army Research Laboratory. The HMS framework is capable of fully asynchronous operation to enable seamless combination of sub-models into highly dynamic hierarchies to form a multi-scale model and has been successfully used to develop many multi-scale applications. In this work, the HMS framework is utilized to develop a multi-scale model of tire-soil interaction consisting of an FEM upper-scale model and DEM lower-scale model. The simulation results demonstrate the proposed FEM-DEM multi-scale method with HMS framework to be fast, accurate and robust for tire-soil interaction mobility simulations.