One thing you can try is to create container records and use them for a parent/child relationship. You can then create a new container record and add X lines where each line is one of the records you're creating. Set the line field values, commit the line and move on. When done, submit the container. You basically create 1k records for the governance of 1 load and save of a single custom record and you're adding lines which is faster than creating records and moving on. If you're expecting other scripts to run on the records, I am not 100% if it still fires the UEs or not for the created child records.. i believe it does.

Does this technique work for mass updating existing records, or only creating new records?

Should work for either as long as the parent/child relationship is there. If its not, just make a new container record and then a ref to that parent on the child record and then you can do it. Once the record is saved and everything is done, you can delete the parent as its only purpose is to be a container.

I believe there's a 10k limit here as well

I've never run into a limit. I've never tried creating 10k records that I can remember. From a technical side, you don't really care about traversing a list in this case. The container is only to get around the limits and is deleted as soon as its committed basically.

Personally I haven't either... But have heard from those in the know

It sounds reasonable @ 10k