Are the up and dw legs still useful in the new E core shape?
Yes, the field seeks to travel shortest path through the low permeability medium (air), so it will close in on itself from the upper and lower tips of the E to the central tip.
Removing the top and bottom bars of the E would reduce permeance (and inductance) a lot more because you would enlarge the airgap by much larger a distance than what you did be removing the I.
Conversely, if you want to achieve an inductance intermediate between the E and EI, you could add the I back, but place few millimeter thick low-permeability shim in the gap to hold it open.
Is there any relation formula of the inductance between the two shapes (EI vs E) so I could rougtly predict the new value?
Sort of. The inductance is proportional to the core permeance. Getting familiar with permeance is a rewarding topic if you need to calculate cores often. If the core permeability is much higher than that of the surrounding medium (as in: steel vs. air), the permeance is essentially proportional to the air gap cross-section divided by air gap length.
Therefore, also inductance would be proportional to the cross-section of the air gap divided by the length of the air gap. If you saw the inductance decrease only by a factor of 4, that means that the airgap in the EI shape was considerable already.
Let's say, if you use a shim to enhance the air gap from 1 mm to 2 mm the factor of reduction would be pretty close to 2. But if you place the E and I further and further apart, the field will start to close between the bars of the E, so the air gap cross-section will be changed and the prediction will be come more difficult.
This proportionality only holds for appreciable air gaps. If air gaps become rather small, the permeance will be less and less reduced due to the air gap, but instead will be limited by the shape of the core itself.