(I)证明:
在图 1 中,因为 $AB=BC=\frac{1}{2}AD=a$,$E$ 是 $AD$ 的中点,且 $\angle BAD = \frac{\pi}{2}$,
所以 $AE = \frac{1}{2}AD = a = BC$,且 $AE // BC$。
又因为 $\angle BAD = 90^\circ$,即 $AB \perp AD$,所以四边形 $ABCE$ 为正方形。
因此,对角线互相垂直,即 $BE \perp AC$。
设 $AC$ 与 $BE$ 交于点 $O$,则 $BE \perp AO$,$BE \perp OC$。
在图 2 中,折叠后 $A_1O$ 对应原来的 $AO$,故仍有 $BE \perp A_1O$。
同时,底面图形未变,故 $BE \perp OC$ 依然成立。
因为 $A_1O \cap OC = O$,且 $A_1O, OC \subset$ 平面 $A_1OC$,
所以 $BE \perp$ 平面 $A_1OC$。
又在直角梯形 $ABCD$ 中,$E$ 为 $AD$ 中点,$BC = \frac{1}{2}AD = ED$,且 $BC // AD$,
所以 $BC // ED$ 且 $BC = ED$。
故四边形 $BCDE$ 为平行四边形,从而 $CD // BE$。
因为 $BE \perp$ 平面 $A_1OC$,且 $CD // BE$,
所以 $CD \perp$ 平面 $A_1OC$。
(II)解:
由已知条件,平面 $A_1BE \perp$ 平面 $BCDE$,且两平面的交线为 $BE$。
由(I)可知 $A_1O \perp BE$,且 $A_1O \subset$ 平面 $A_1BE$。
根据面面垂直的性质定理,可得 $A_1O \perp$ 平面 $BCDE$。
即 $A_1O$ 为四棱锥 $A_1-BCDE$ 的高。
在正方形 $ABCE$ 中,边长为 $a$,对角线 $AC = \sqrt{a^2+a^2} = \sqrt{2}a$。
$O$ 为对角线交点,故 $A_1O = AO = \frac{1}{2}AC = \frac{\sqrt{2}}{2}a$。
底面四边形 $BCDE$ 为平行四边形,其面积 $S_{BCDE}$ 可以看作是以 $BC$ 为底,$AB$ 为高的平行四边形面积(或者两个全等三角形面积之和):
$S_{BCDE} = BC \cdot AB = a \cdot a = a^2$。
四棱锥 $A_1-BCDE$ 的体积 $V$ 为:
$$ V = \frac{1}{3} S_{BCDE} \cdot A_1O = \frac{1}{3} \cdot a^2 \cdot \frac{\sqrt{2}}{2}a = \frac{\sqrt{2}}{6}a^3 $$
由题设知 $V = 36\sqrt{2}$,故:
$$ \frac{\sqrt{2}}{6}a^3 = 36\sqrt{2} $$
$$ \frac{1}{6}a^3 = 36 $$
$$ a^3 = 216 $$
解得 $a = 6$。