Granular deposit instabilities are ubiquitous in nature; they display solid or fluid-like behavior as well as catastrophic events such as avalanches, mud flows or land slides. Recent laboratory-scale avalanche experiments on an erodible substrate are treated in the framework of ``partial fluidization'' model of dense granular flows. The model identifies a family of propagating soliton-like avalanches with shape and velocity controlled by the inclination angle and the depth of substrate. At high inclination angles the solitons display a transverse instability, followed by coarsening and fingering similar to recent experimental observation. A primary cause for the transverse instability is directly related to the dependence of soliton velocity on the granular mass trapped in the avalanche.