Successful transition to renewable energy supply depends on the development of cost-effective large-scale energy storage technologies. Renewable energy can be converted to (or produced directly in the form of) green gases, such as hydrogen. Subsurface formations offer feasible solutions to store large-scale compressed hydrogen. These reservoirs act as seasonal storage or buffer to guarantee a reliable supply of green energy in the network. The vital ingredients that need to be considered for safe and efficient underground hydrogen storage include reliable estimations of the in-situ state of the stress, especially to avoid failure, induced seismicity and surface subsidence (or uplift). Geological formations are often highly heterogeneous over their large (km) length scales, and entail complex nonlinear rock deformation physics, especially under cyclic loading. We develop a multiscale simulation strategy to address these challenges and allow for efficient, yet accurate, simulation of nonlinear elastoplastic deformation of rocks under cyclic loading. A coarse-scale system is constructed for the given fine-scale detailed nonlinear deformation model. The multiscale method is developed algebraically to allow for convenient uncertainty quantifications and sensitivity analyses.