Symbolic regression using genetic programming (SRGP) is one of the most popular machine learning approaches for building human-readable interpretable models. At the same time, SRGP usually fails in solving high-dimensional problems. Large-scale problems lead to rapid bloating of trees and require special techniques for preventing always-destructive genetic operations and the loss of variables in trees. In the study, we have proposed a novel approach, which performs random decomposition of large-scale symbolic regression problems into sub-problems with less number of variables and uses cooperative coevolution for merging sub-solutions at the fitness evaluation stage. We have discussed the general conception and some alternative realizations. The results of numerical experiments using some large-scale artificial and real-world benchmark problems have demonstrated that the proposed approach outperforms the standard SRGP algorithm and some of its variations.