Context. Part of the very high energy γ-ray radiation coming from extragalactic sources is absorbed through the pair production process on the extragalactic background light photons. Extragalactic magnetic fields alter the trajectories of these cascade pairs and, in turn, convert cosmic background photons to γ-ray energies by inverse Compton scattering. These secondary photons can form an extended halo around bright VHE sources. Aims: We searched for an extended emission around the bright blazars Mrk 421 and Mrk 501 using the MAGIC telescope data. Methods: If extended emission is present, the angular distribution of reconstructed γ-ray arrival directions around the source is broader than for a point-like source. In the analysis of a few tens of hours of observational data taken from Mrk 421 and Mrk 501 we used a newly developed method that provides better angular resolution. This method is based on the usage of multidimensional decision trees. Comparing the measured shapes of angular distributions with those expected from a point-like source one can detect or constrain possible extended emission around the source. We also studied the influence of different types of systematic errors on the shape of the distribution of reconstructed γ-ray arrival directions for a point source. Results: We present upper limits for an extended emission calculated for both sources for various source extensions and emission profiles. We obtain upper limits on the extended emission around the Mrk 421 (Mrk 501) on the level of <5% (<4%) of the Crab Nebula flux above the energy threshold of 300 GeV. Using these results we discuss possible constraints on the extragalactic magnetic fields strength around a few times 10-15 G.