We report our intensive radio monitoring observations of the jet in M87 with the VLBI Exploration of Radio Astrometry (VERA) and the European VLBI Network (EVN) from February 2011 to October 2012, together with contemporaneous high-energy gamma-ray light curves obtained by the Fermi-LAT. During this period, an elevated level of the M87 flux is reported at VHE gamma rays. We detected a remarkable increase of the radio flux density from the unresolved jet base (radio core) with VERA at 22 and 43GHz coincident with the VHE activity. Meanwhile, we confirmed with EVN at 5GHz that HST-1 (an alternative gamma-ray production candidate site) remained quiescent in terms of its flux density and structure. These results in the radio bands strongly suggest that the VHE gamma-ray activity in 2012 originates in the jet base within 0.03pc or 56 Schwarzschild radii from the central supermassive black hole. We further conducted VERA astrometry for the M87 core during the flaring period, and detected core shifts between 22 and 43GHz. We also discovered a clear frequency-dependent evolution of the radio core flare at 43, 22 and 5GHz; the radio flux density increased more rapidly at higher frequencies with a larger amplitude, and the light curves clearly showed a time-lag between the peaks at 22 and 43GHz. This indicates that a new radio-emitting component was created near the black hole in the period of the VHE event, and then propagated outward with progressively decreasing synchrotron opacity. By combining these results, we estimated an apparent speed of the newborn component, and derived a sub-luminal speed of less than ~0.2c. This value is significantly slower than the super-luminal (~1.1c) features that appeared from the core during the prominent VHE flaring event in 2008, suggesting that the stronger VHE activity can be associated with the production of the higher Lorentz factor jet.