If I can only power the chip with 5v, how on earth could I use it to control 12v LEDs?
AFAIK, there is no such thing as a 12V LED, unless it has external components added in some package. So dont bother splitting supplies for that reason. I'd only worry about making sure you dont draw to much current from the Arduino's supply. I would control the LED's with transistors if they use much current, that way you can power them with an external 5 or 12 volts. A ULN2003 transistor array or similar (I use ULN2803) makes this very easy to do with a minimum of components.
Back to the question on why your LED's worked on 12V: because you are probably powering them from the Arduino output pins, which means there's actually 5V going to the LED's