We use Local Group galaxy counts together with the ELVIS N-body simulations to explore the relationship between the scatter and slope in the stellar mass vs. halo mass relation at low masses, $M_\star \simeq 10^5 - 10^8 M_\odot$. Assuming models with log-normal scatter about a median relation of the form $M_\star \propto M_\mathrm{halo}^\alpha$, the preferred log-slope steepens from $\alpha \simeq 1.8$ in the limit of zero scatter to $\alpha \simeq 2.6$ in the case of $2$ dex of scatter in $M_\star$ at fixed halo mass. We provide fitting functions for the best-fit relations as a function of scatter, including cases where the relation becomes increasingly stochastic with decreasing mass. We show that if the scatter at fixed halo mass is large enough ($\gtrsim 1$ dex) and if the median relation is steep enough ($\alpha \gtrsim 2$), then the "too-big-to-fail" problem seen in the Local Group can be self-consistently eliminated in about $\sim 5-10\%$ of realizations. This scenario requires that the most massive subhalos host unobservable ultra-faint dwarfs fairly often; we discuss potentially observable signatures of these systems. Finally, we compare our derived constraints to recent high-resolution simulations of dwarf galaxy formation in the literature. Though simulation-to-simulation scatter in $M_\star$ at fixed $M_\mathrm{halo}$ is large among separate authors ($\sim 2$ dex), individual codes produce relations with much less scatter and usually give relations that would over-produce local galaxy counts.