The main gain would be that it would be easier to divide CPU tasks into multiple threads, without having to solve all the difficult issues with accessing the graphics API. Normally you either would have to make the context current (which might have bad performance implications) or provide a queue and call the graphics api in a single thread. I don't think that any performance is gained this way, because the GPU indeed processes them sequentially anyway, but it makes the developer job a lot easier.
The reason that it was not done until now probably is because directx and opengl were created in a time where multithreading was not really apparent. Also the Khronos board is very conservative in changing the API. Their view on Vulkan is also that it will coexist next to OpenGL, because both serve different purposes. It probably was not until recently that paralism became so important, as consumers get access to more and more processors.
EDIT: I don't mean that no performance is gained from doing work in multiple CPUs, it is not useful to split your calls into multiple threads to create textures/shaders faster. Rather the performance is gained due to having more processors busy and keeping the gpu busy with things to perform.