Stars with unusual properties can provide a wealth of information about rare stages of stellar evolution and exotic physics. However, determining the true nature of peculiar stars is often difficult. In this work, we conduct a systematic search for cool and luminous stars in the Magellanic Clouds with extreme variability, motivated by the properties of the unusual Small Magellanic Cloud star and Thorne-(Z) over dotytkow Object (T(Z) over dotO) candidate HV 2112. Using light curves from ASAS-SN, we identify 38 stars with surface temperatures T < 4800K, luminosities log(L/L-circle dot) > 4.3, variability periods >400 days, and variability amplitudes Delta V > 2.5 mag. Eleven of these stars possess the distinctive double-peaked light-curve morphology of HV 2112. We use the pulsation properties and derived occurrence rates for these 12 objects to constrain their nature. From comparisons to stellar populations and models, we find that one star may be a red supergiant with large-amplitude pulsations. For the other 11 stars, we derive current masses of similar to 5-10 M-circle dot, below the theoretical minimum mass of similar to 15 Me for T(Z) over dotOs to be stable, casting doubt on this interpretation. Instead, we find that the temperatures, luminosities, mass-loss rates (MLRs), and periods of these stars are consistent with predictions for super-asymptotic giant branch (s-AGB) stars that have begun carbon burning but have not reached the superwind phase. We infer lifetimes in this phase of similar to(1-7) x 10(4) yr, also consistent with an s-AGB interpretation. If confirmed, these objects would represent the first identified population of s-AGB stars, illuminating the transition between low- and high-mass stellar evolution.