We have demonstrated the frequency dependence of the tunnel-type magneto-dielectric (TMD) effect in superparamagnetic Cox-(MgF2)1-x granular nanostructures by precise variations of x from 0.06 to 0.2. The structures consist of the nanometer-sized Co granules embedded in a crystallized MgF2 dielectric matrix. We observed an increased peak dielectric change Δϵ′/ϵ′0 from 0.8% to 3% at a specific frequency fTMD, and tunable fTMD was achieved from 8 kHz to 6.6 MHz by increasing x. Theoretical fittings predict that the narrow distribution of relaxation time gave rise to an enhanced Δϵ′/ϵ′0 and the narrowing of fTMD; the position variation of fTMD was attributed to the change in the intergranular distance between a pair of two neighboring granules. This study may help understand the fundamental physics between the TMD effect and nanometric structure and indicate that the films may work at higher frequency for devices with tunable dielectrics.