We report the results of several programs to study the variability of high-velocity (up to 0.2c) mini-"broad absorption lines" (mini-BALs) and BALs in quasar spectra, and thus to better characterize the structural and physical properties of these outflows. After the report of a highly variable mini-BAL outflow at a speed of ~0.17c in the quasar PG0935+417, we created the first systematic accounting of outflows in Sloan Digital Sky Survey (SDSS) quasar spectra that includes mini-BALs and extremely high velocity outflows (up to 0.2c) to measure their frequency. Following this study, we began a monitoring campaign to study the location, and dynamical and evolutionary effects of these outflows. This program covers a range of 0.9-3.3 years in the quasars' rest-frame by comparing new spectra (using facilities at the Kitt Peak National Observatory and MDM Observatory) with archival SDSS spectra. We find that ~57% of quasars with mini-BALs and BALs varied between just two observations. This variability tends to occur in complex ways; however, all the variable lines vary in intensity and not in velocity, not finding evidence for acceleration/deceleration in these outflows. Due to the variations in strength, mini-BALs can become BALs and vice versa, suggesting they share a similar nature. We include as an example the discovery of the transition of a mini-BAL into a BAL in the spectra of the SDSS quasar J115122+020426.