It took me an evening to figure this out, particularly because I didn't want to use command line to slice up my image. So I wanted to share my findings here.
The most solid guide is Oliver Marriott's Using Leaflet.js with non-geographic imagery. His was the method I used in the end, except that I couldn't get his TileUp tool to work. Luckily, I have Photoshop and Bramus' Google Maps Tile Cutter script did the job of slicing up my image. The one I had to do there was make sure my image's width and height were multiples of 256 pixels so that it slices nicely.
Another guide I found is Pedro Sousa's Zoomable image with Leaflet. This was a little more out of date – the Leaflet version was 0.4 rather than 0.6, and the MapTiler software he recommends no longer really does what he wants (and is no longer free).
There's also another method altogether; to not use tiles but just one big image. This may be useful (and faster) for some cases where there's not much zoom. Paulo Vieira has published his solution on Google Groups here.
I didn't have a chance to try out Bjørn Sandvik's Zoomify + Leaflet solution (I wanted more control over my intermediate zoom levels and didn't like the folder structure of Zoomify). His Leaflet plugin may make this just as easy as the solution I went ahead with.
Lastly, I also ran into this problem with having zoom levels above 18 for some reason. I didn't test it out too much, since it seemed easier to just use lower numbers when I only had a 5 zoom levels.