Where is the XML Slideshow specification?

I don't know that there is one—I certainly couldn't find anything official, though I haven't asked a GNOME mailing list, or looked at the source code, to be sure.

I figured out what I needed from the Cosmos set [1] initially and, later, edren's "All Day Long (Animated Wallpaper)" [2], and my own experiments [3].

[1] /usr/share/backgrounds/cosmos/background-1.xml
    (alternates static and transition elements)
[2] http://gnome-look.org/content/show.php?content=83443
    (shows <static> isn't required)
[3] (showed <transition> wasn't required either)

I was looking if Create Background Slideshow could make random
slideshows, when I select a set of pictures, it shows them all without
an specific secuence. Then, it came to my mind, if the specification
already allows this, or if it has to be pre-shuffled in the app.

Create Background Slideshow (CreBS) only creates the XML files, then GNOME reads the selected one and displays each image and transition—in order—and, as far as I know, there is no way to tell GNOME to display the images randomly.

You could mix up the images in CreBS (a simple way to do this has already been requested [1]) and re-apply the wallpaper, but GNOME will continue to go through them in that new order.

If a shuffle feature is added to the command-line options in the future, then you could have a script run crebs to re-open, shuffle, and re-apply the slideshow at regular intervals.

For now, though, the best solution I can offer is a pseudo-random one. It would require a few minutes' work, but it should achieve a passable result:
Copy each image 5 or 6 times and then mix the images up.
That way each time any particular picture is shown there will be several possible successors, giving the appearance of randomness.

[1] https://answers.launchpad.net/crebs/+question/114105