Draining water from an upward drain
Use a drain pump kit

Since asking your water softener to try to drain up that far unaided is crazy, as they are gravity-draining appliances to begin with, this needs to be corrected properly, even outside of an icing climate.  The good news is that since the water softener won't run without electric power anyway, we can safely use a drainage pump kit (laundry sink/washer drain kit) to motivate the wastewater from your softener to go uphill, without worrying about an overflow if the power goes out.