We have studied the effects of shattering in grain-grain collisions. Based upon extensive numerical simulation of surface explosions and impacts, an analytical model has been developed which relates the final crater mass and fragment size distribution to the relative collision velocity, grain sizes, and material properties of projectile and target. Our model contains one free parameter, the critical shock pressure for shattering. We have compared the calculated crater masses to laboratory experiments on (sub)micron-sized particle impacts on a wide variety of materials and find good agreement assuming that the critical pressure for shattering is equal to the shear strength of the material. This critical pressure corresponds to minimum collision velocities of similar to 1 km s(-1) for shattering to occur. The shattering threshold is much smaller than the vaporization threshold, and we therefore conclude that shattering dominates over vaporization in grain-grain collisions. The calculated size distribution of the shattered fragments scales with a(-3.3); slightly less steep than the Mathis, Rumpl, & Nordsieck (MRN) size distribution. Essentially, any shattering model where the size of the fragments is related to the pressure experienced will lead to fragment power-law size distributions with indices slightly steeper than similar to 3. The maximum fragment size increases with increasing crater size (i.e., increasing collision velocity) until the target grain is completely disrupted by the collision. For higher velocity collisions, our theory predicts that the maximum shattered fragment size will decrease again. Dust destruction (return of grain mass to the gas) in the interstellar medium occurs predominantly in shock waves in the warm neutral/ionized medium (density similar or equal to 0.25 cm(-3), temperature similar or equal to 10(4) K). The new theory for grain shattering in grain-grain collisions has been incorporated into a grain destruction code and used to reevaluate the grain destruction rate in interstellar shocks in the warm medium, We find that, for all the grain materials we consider (graphite, silicate, silicon carbide, diamond, iron, and ice) nonthermal and thermal sputtering dominate the grain destruction. We also find that grain disruption (shattering) in grain-grain collisions dominates the grain mass redistribution. We present detailed results for grain destruction as a function of the grain size and composition. In particular, we consider MRN size distributions of silicate and carbonaceous (amorphous carbon/graphite) grains. We also present results for silicon carbide, diamond, iron, and ice test particles. For both carbonaceous and silicate grains we find that the fractional destruction (i.e., return of solid material to the gas phase) is less than or equal to 0.5, for upsilon(s) less than or equal to 200 km s(-1). The grain lifetimes against destruction, assuming the three-phase model of the interstellar medium, are 6 x 10(8) yr, and 4 x 10(8) yr, for carbonaceous and silicate grains, respectively, only slightly longer than previous studies that ignored shattering. Grain shattering in grain-grain collisions in shock waves leads to the redistribution of the dust mass from large grains(a greater than or equal to 1000 Angstrom) into small grains (a<500 Angstrom). After processing by a single shock, a major fraction of the grains larger than 300 Angstrom have experienced shattering grain-grain collisions. The slope of the fragment size distribution produced in single collisions has little influence on the size distribution produced by shocks. Essentially, the resulting grain size distribution is slightly steeper than MRN, because the largest grains move at the highest postshock velocities and hence are preferentially shattered into the smallest fragments. Large grains are lost from the interstellar grain size distribution on time scales less than 10(8) yr in the warm medium. For 50 km s(-1) less than or equal to upsilon(s) less than or equal to 200 km s(-1) as much as 5%-15% of the initial grain mass (all grain radii greater than or equal to 50 Angstrom) may end up in sub-14 Angstrom fragments. Thus, interstellar shocks may be a prodigious source of PAH molecules, PAH clusters, and small grains. Given that the typical stardust injection time scale is 2.5 x 10(9) yr, we conclude that efficient mechanisms for grain growth, and in particular, the reformation of grains with radii greater than or equal to 1000 Angstrom must exist in interstellar medium in order that the refractory elements be incorporated in dust and that most of the dust mass is in sizes greater than or equal to 1000 Angstrom as observed.