We investigate colossal magnetoelectric coupling through interactions between ferroelectric and ferromagnetic nanodomains in 3-1 multiferroic BaTiO3/CoFe2O4 nanocomposites using a recent real-space phase field model based on the Landau-Ginzburg theory. A hierarchical ultrafine domain structure is characteristically formed in the nanocomposites, resulting in an extremely high density of domain walls, which causes polarization domains to be more susceptible to an external magnetic field via interfacial strain-mediation. This leads to an anomalously large magnetoelectric coupling effect in the multiferroic nanocomposites. We further demonstrate that the domain configuration and consequent magnetoelectric effect are strongly dependent on the constituent phase distribution, suggesting a promising route for the rational design of multiferroic domains and magnetoelectric effects, reminiscent of recent nano-metamaterial concepts.