We have obtained deep photometry in two 1x1 degree fields covering the close pair of dwarf spheroidal galaxies (dSph) Leo IV and Leo V and part of the area in between. We find that both systems are significantly larger than indicated by previous measurements based on shallower data and also significantly elongated. With half-light radii of r_h=4.6 +- 0.8 (206 +- 36 pc) and r_h=2.6 +- 0.6 (133 +- 31 pc), respectively, they are now well within the physical size bracket of typical Milky Way dSph satellites. Their ellipticities of epsilon ~0.5 are shared by many faint (M_V>-8) Milky Way dSphs. The large spatial extent of our survey allows us to search for extra-tidal features with unprecedented sensitivity. The spatial distribution of candidate red giant branch and horizontal branch stars is found to be non-uniform at the ~3 sigma level. This substructure is aligned along the direction connecting the two systems, indicative of a possible `bridge of extra-tidal material. Fitting the stellar distribution with a linear Gaussian model yields a significance of 4 sigma for this overdensity, a most likely FWHM of ~16 arcmin and a central surface brightness of ~32 mag arcsec^{-2}. We investigate different scenarios to explain the close proximity of Leo IV and Leo V and the possible tidal bridge between them. Orbit calculations demonstrate that they are unlikely to be remnants of a single disrupted progenitor, while a comparison with cosmological simulations shows that a chance collision between unrelated subhalos is negligibly small. Leo IV and Leo V could, however, be a bound `tumbling pair if their combined mass exceeds 8 +- 4 x 10^9 M_sun. The scenario of an internally interacting pair appears to be the most viable explanation for this close celestial companionship. (abridged)