The bug
See title, saving a structure with a sub folder (eg "test/test") returns "unable to save structure" if the folder does not exist (it works fine if the folder exists).
Code analysis
TemplateManager.writeTemplate(MinecraftServer server, ResourceLocation id) returns false if creating a new instance of FileOutputStream throws a FileNotFoundException when the specified directory does not exist.
Fixed in some 1.13 snapshot.