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 SMC star and Thorne-.Zytkow Object (T.ZO) candidate HV2112. Using light curves from ASAS-SN we identify 38 stars with surface temperatures T $<$ 4800K, luminosities $log$(L/L$_odot$) $>$ 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 HV2112. 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 $sim$5-10 M$_{odot}$, below the theoretical minimum mass of $sim$15 M$_{odot}$ for T.ZOs to be stable, casting doubt on this interpretation. Instead, we find that the temperatures, luminosities, mass-loss rates, 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 $sim($1$-$7) $times$ 10$^{4}$ years, 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.