What is the connection between mechanics and electrodynamics that makes it necessary for both of these to obey the same principle of relativity? Mechanics obeyed Newtonian relativity (faithful to Galilean transformations) before Einstein.
Einstein formulated Special relativity (faithful to Lorentz transformations), and Maxwell's equations became invariant under Special relativity. So, electrodynamics obeyed Special relativity. So far, so good.
Why could we not be happy to conclude that Mechanics obeys Newtonian relativity, and Electrodynamics obeys Special relativity? Why in his first postulate did Einstein emphasize that both Mechanics and Electrodynamics should obey Special relativity? What was the crucial connection between Mechanics and Electrodynamics that demanded that both should obey the same principle of relativity? Is the reason primarily based on experimental verification of Newton's laws for high velocity particles?
 A: Einstein introduces his 1905 paper On the Electrodynamics of Moving Bodies with a description of an electromechanical system. He presents the well-known fact (at least to electrical engineers) that the relative motion of a magnet and a coil of wire determines their interaction as motivation for his development of relativity.
I find it curious that this approach has vanished into the mists of history.
Of course, we must acknowledge that the inconsistencies that Einstein saw in combining Galilean relativity with electrodynamics don't bother actual designers of electromechanical devices. An electrical engineer designing a motor is going to calculate the mechanical parts using Newtonian principles even as they use electrodynamics (but ignoring displacement current for even more inconsistency) to calculate the electrical parts. The quantitative consequences of the inconsistencies are too small to matter.
However, there are many other systems of interest to physics where one absolutely must calculate on a proper relativistic foundation to get the answer that matches reality. That's the real reason we accept relativity. Experimental results justify the math.
A: 
Why could we not be happy to conclude that Mechanics obeyed Newtonian relativity, and Electrodynamics obeyed Special relativity?

If mechanics obeyed Galilean relativity and electrodynamics obeyed special relativity, then you could imagine constructing some sort of part mechanical / part EM coupled device. Now when we consider a Galilean transformation, the EM part of the device would fail to be invariant, so the device is not Galilean invariant. When we consider a Lorentz transformation, the mechanical part of the device would fail to be invariant, so the device is not Lorentz invariant.
Thus, we could construct something that is neither Galilean invariant nor Lorentz invariant. If we imagine the possibility of a third kind of relativity invariance, then it would have been manifest in mechanics and EM alone beforehand. Since we know Newtonian mechanics obeys Galilean relativity only and EM obeys Lorentz invariance only, we know there isn't any "third type" of relativity invariance.
Thus, if mechanics and EM obeyed different relativity principles, then we would be forced to conclude that the universe as a whole did not obey any relativity principle. Einstein was motivated by the belief that some relativity principle is true, leading him to revise mechanics for this reason.
Of course, the question ends up being an empirical matter, because at the time people thought the possibility of an absolute reference frame was plausible. If you're ok with mechanics and EM obeying different relativity laws, then you have to bite the bullet and say that relativity as a whole is wrong. That would have been a plausible stance to take in the 1900s.  However, Einstein disagreed and was proven to be correct in the end.
A: Maybe just to emphasize the main point of Andrew steane's answer: The crucial connection is that charged particles are both mechnaical and electrodynamical objects.
Assume that you have some reference frame where you consider a bunch of charged particles. They will move according to ther mechanical equations of motions under the mutual forces determined by the electromagnetic fields, which are, in turn, generated by the charge particles themselves.
If mechanical and electrodynamical would change differently under changes of reference frame, this picture would change, and either the mechanical or the electrodynamical laws (or both) would have to change.
A: Logically, one could assert the relativity principle first, and then develop theories which respect the principle. In fact this is how we typically do physics. In this way both relativistic mechanics and electrodynamics both follow from the postulates of relativity plus a few other assumptions such as simplicity and some general notion of Lagrangian methods.
If one tried to construct physics with mechanics obeying some sort of Galilean version of relativity then one would have some very odd contortions to get around, since electromagnetic forces are at work inside all ordinary solid and liquid entities. How could those entities respect one version of physics while the forces inside them respect another? It probably cannot be made to make sense.
A: For the argument you have raised, I hope you have got your answers from above. Just to make things clear I will be giving you a classic example that connects mechanics, electromagnetism and relativity.
The example is of production of electricity using a ring magnet, a wire and a galvanometer.
Insert the wire inside the ring magnetic and connect it's ends to galvanometer completing the circuit.
Case1:
Move the magnet relative to wire.
Case2:
Move the wire relative to magnet.
In both the above cases, deflection can be seen in galvanometer stating that reference frames don't matter in this experiment, which is accordance to Relativity.
Hope this helps.
A: 
Mechanics obeyed Newtonian relativity (faithful to Galilean transformation) before Einstein.

This isn't just wrong, it's exactly backwards. Mechanics do not obey any man-made law or equation, the various laws describe mechanics. Newtonian and Galilean equations adequately described most of the observed mechanical interactions, since almost all variance from their predictions was below the level of accuracy of available measurements. There were a few exceptions however that couldn't be explained away as inaccurate measurement or bad calculations, and Einstein's SR equations filled in most (if not all) of those gaps.
The most obvious example of a previously unexplained phenomenon that GR resolved was the orbit of Mercury. While all of the other observed orbits were very well calculated by Galileo and Newton, Mercury stubbornly refused to align itself to their equations. It wasn't until we factored in GR effects that we found an explanation for why, and were finally able to accurately calculate the orbit from base data rather than mere observation.
A: The common denominator is that both electromagnetic and mechanical phenomena occur in space and time. Special relativity accounts for the unvarying speed of light by explaining that the geometry of space and time is not Euclidian, so all processes in physics which involve functions of space and time will be affected by that.
A: 
What is the connection between mechanics and electrodynamics

The connection is that those are the same thing.
We know of four fundamental forces acting within the universe to make up everything we see and know: the electromagnetic force, the weak nuclear force, the strong nuclear force, and gravitation.
When talking about mechanics (i.e., our everyday, macroscopic objects ranging from spoons and forks, via machines, up to planets and everything else), we are talking about atoms interacting via one or more of those forces.
For your question, we can mostly ignore the weak and strong force (they act on a subatomic scale) and gravity (as long as we are not talking about black holes, supermassive stars etc., where gravity becomes strong enough to cancel out the other forces in a catastrophic matter).
This leaves us with the electromagnetic force. Atoms, together with electromagnetism, is what makes up everything we know, see, interact with in our daily lives. Everything from light, to electricity, to the fact that you are standing on the floor and not sinking into it, to friction, to the normal phases of matter (solid - fluid - gas ...), to combining atoms into molecules, and so on and forth, is all just atoms mixed with electromagnetism.
The reason why solid matter is solid, why metals behave like they do, how fluids flow, how gases disperse and so on, can all be explained just with electromagnetism (obviously gravity plays a role if planets or stars happen to be around, but it's just a sideshow).
As an example, the fact that the earth does not collapse on itself is because electromagnetism is there to resist the pull of gravity, hence leading to a solid but still somewhat loosely held together clump of material, instead of a black hole.
Therefore, your question "why do mechanics and electrodynamics both behave relativistic" is trivially answered by "because they are the same in the sense that they are based on the same objects (atoms) and electromagnetic force between them".
A: The principle itself is the connection and not the other way around.
The principle of relativity is the idea that the state of constant speed of a reference frame must be impossible to detect from within, i.e, if you don’t witness acceleration by yourself, then you’re doomed to be ignorant about who was accelerated among bodies with constant speed. In fact one could argue that the speed of light (second Einstein’s postulate) was deemed to be constant because, if not, it could be used to verify if one was accelerated in the past even if that person didn’t witness it. As an intrinsic property of our universe not only mechanics or electrodynamics must obey it, everything imaginable must obey this same idea, including your aging, pleasure, or whatever you can think of.
