The ultrafast relaxation of small clusters immediately after ultrashort single ionization is studied. We use an electronic model and molecular dynamics simulations to:analyze the ionization induced fragmentation dynamics of small Hg, clusters. Our results show that fragmentation consists mainly in emission of single atoms. We also find a remarkable. difference between this nonequilibrium unimolecular dissociation and that described by the Rice-Ramsperger-Kassel-Marcus theory. For fixed cluster size, we determine the time-dependent fragmentation probability of a cluster ensemble as a function of the temperature before ionization. A dramatic change of the fragmentation behavior occurs when the temperature;before ionization reaches the "melting temperature" of the neutral clusters. For all cluster sizes studied, the temperature dependence of the average fragmentation times after ionization shows a remarkable correlation with the root-mean-square bond length fluctuations delta(T) of the Clusters before ionization. This new effect reflects sensitivity of the ultrashort-ionization induced fragmentation dynamics to the melting dynamics of the neutral clusters.