"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.