It's not the gallons that would be the issue. It's the lack of tankmates. You have to be extremely creative to get away with just two individual, mature cichlids together. Especially when they're use to being alone, and male. Decor must be full, and you almost want it to form breaks in the tank so that they don't really see each other much. Dithers and/or additional cichlids are your best bet though. You need other fish to take the focus of those two off each other. Even though it was not the most ideal way, chalk one down for lesson learned.