"First Aid found corruption that needs to be repaired"

Fixed my own problem:

I went into internet recovery mode (Cmd+Option+R) on startup and was able to repair the disk from disk utility inside of internet recovery. I guess it was cause recovery was on the disk I was trying to fix.

One key point that was left out - you have to mount the disk when using disk utility in recovery mode

Full solution:

1. Power down
2. Restart in internet recovery mode (cmd + opt + R)
3. Select disk utility
4. Select the SSD
5. Click “mount”
6. Run first aid
7. Restart

I was trying without mounting the disk. First Aid would appear to run like normal, but didn’t find anything to correct. Mounting the disk first enables First Aid to find and repair the issues.