Disclaimer: I'm a physicist and not an historian.

So... Einstein was hugely influential in that he wrote to the president to warn him about the possibility that the Germans were building an atomic bomb, and this was a factor that resulted in the start of the Manhattan project.

Regarding the impact of the theory of relativity, instead, I wouldn't really know, I'm not aware of sources that explore this. Anyway, I can tell you that back then (starting about 1900) was a time of huge revolutions in physics. Discoveries in different fields happened one right after another, sometimes in apparently independent fields. So... Theory of special relativity, with its E=mc^2, is fundamental to justify how can nuclear reactions deliver so much energy. Otherwise it couldn't be explained in any way! Yet again, even today, nuclear physics is usually handled without taking relativity into account. Research on nuclear physics, particle physics and x-rays was already going on independently from relativity at a full pace. Radioactivity was already known, somehow, in 1902. The first cross-over between quantum mechanics and relativiy, the Dirac equation that accounted for particles at relativistic speeds, was developed only in 1928 and it was important only for particle physics, not for standard nuclear reactions.

Therefore I'd guess that they would have been able to build a bomb even without knowing relativity at all. (indeed no relativistic knowledge is needed to build one at any time, if one is fine with knowing that starting from x grams of uranium one obtains x-y grams of other elements and lots of energy, without asking himself how it's possible to convert energy into matter.)

Since you seem interested primarily in the historical context of making atomic bombs, here's a rough overview with relation to Einstein:

• 1895, Röntgen discovers X-rays. People say, "whoa, there is a whole invisible physical world to probe!"

• 1898, Becquerel finds that X-ray like emissions come out of uranium. The Curies look into this and dub the phenomena radioactivity. They recognize that in some substances, e.g. radium, the amount of energy being released is tremendous compared to the volume of the atoms in question — that it is much, much more energetic than any chemical combustion, but it is hard to extract that energy because you can't make it all be released at once. Soddy and Rutherford determine ca. 1900 that this is because of atomic transmutation, i.e. the atom is breaking down. They also start some of the first experiments to modify atomic compositions.

• 1905, Einstein publishes his four papers that constitute Special Relativity. One of them derives the mass-energy relationship. It is interesting but has no obvious applications. The two papers that get the most attention from this series is the one on the photoelectric effect, which helps establish the physical reality of the "quantum," and his work on the Lorentz contraction which discards with the idea of a preferred "rest frame" and the aether. (Neither have anything specific to do with atomic bombs.)

• 1909, Rutherford et al. do experiments which imply that atoms contain most of their mass in a centralized nucleus, surrounded by whirring electrons. This work is important both for its establishment of an influential (if problematic) atomic model, but also its illustration of the value of using radioactive particles (e.g. alpha particles) as experimental tools.

• 1913, Bohr modifies Rutherford's atomic model, replacing the whirring electrons with electrons in stable orbits that make "quantum leaps" between orbits. This resolves some of the problems with Rutherford's model but raises new questions (e.g. why are some orbits stable and some not?).

• 1915: Einstein publishes his General Theory of Relativity, which is essentially a theory of gravity. It has nothing to do with energy release. In 1918 it is apparently confirmed by observations by Eddington which catapults Einstein into a celebrity level of scientific stardom.

• 1910s-1920s: Bohr, Heisenberg, and others develop quantum mechanics. This is distinctly different from the quantum theory of Einstein and Planck. It is full of many unintuitive notions regarding the nature of information, the nature of reality, and the nature of physical theory itself. Einstein hates it and has many impassioned disputes with Bohr about it. (Einstein doesn't disagree with the quantitative results but refuses to believe in a universe where anything is fundamentally unknowable.)

• 1932: Lawrence invents and builds the cyclotron, the first of a new type of high-energy particle accelerator — a machine that lets researchers shoot various particles at targets and see the results. Over the course of the 1930s Lawrence builds successively larger accelerators that allow for higher energies to be achieved, and are used to explore many new atomic and subatomic phenomena.

• 1932: Chadwick establishes the existence of the neutron, a neutrally-charged subatomic particle in the atomic nucleus. It immediately is obvious that it will be a valuable new tool for probing how atoms are made, because of its lack of an electrical charge. (Protons are positively charged and thus repel one another; electrons are repelled by other electrons. Neutrons are repelled by nothing.)

• 1934: The Joliot-Curies announce their discovery of artificial radioactivity — that bombarding elements with radioactive particles can change their atomic makeup and make them radioactive in turn.

• 1934: Fermi conducts experiments involving the irradiation of uranium with neutrons. He finds that when the neutrons are slowed down (moderated, in modern terminology) by first bouncing off of lighter atoms (e.g. carbon and oxygen), they are more readily absorbed. He observes radioactivity after shooting uranium with the neutrons and concludes that new heavy elements are being created.

• 1938: The chemists Hahn and Strassmann, in Berlin, finalize their work that replicates Fermi's experiment but use very subtle and careful nuclear chemistry techniques to isolate the byproducts of the uranium + neutrons reaction. They do not find new heavy elements, they find only unusually radioactive light elements (like barium). They find this inexplicable. Hahn writes to Meitner (a Jewish physicist who worked in their lab but was exiled to Sweden by the Nazis) to ask for her interpretation. She discusses this with her nephew, Frisch, and they conclude the uranium atoms must be splitting. They use E=mc^2 to calculate the predicted energy release — a lot per individual atom, though still not a lot from a human point of view. They dub this splitting process "fission."

• Early 1939: Hahn, Strassmann, Meitner, and Frisch publish papers on nuclear fission. Physicists around the world are fascinated and shocked — it is an entirely new, unexpected physical process. Some suspect that maybe there is a lot of energy that can be released from it but most think that industrial applications are decades off. A few start to wonder about weapons. Szilard, a Hungarian physicist in exile in the USA, immediately suspects a bomb may be possible, because he has long been thinking about the possibility of neutron-based nuclear chain reactions. He attempts to convince other non-German scientists to not publish on the possibility of using fission in a weapons context, and is largely successful.

• Spring 1939: Joliot-Curie and his team do not agree with the self-censorship and publishes evidence (the number of secondary neutrons per fission) that implies that nuclear weapons may be possible. Bohr and Wheeler publish the first theoretical treatment of fission which establishes that two isotopes of uranium are involved and that only one of them is fissionable by both fast and slow neutrons (U-235). They conclude that making an atomic bomb would be extremely difficult.

• Late 1939: Szilard, frustrated that most physicists in the USA are not taking the idea of an atomic bomb seriously — and the idea that the Germans might be able to get one — goes to Einstein and tells him of his fears. Einstein agrees to collaborate with Szilard on a letter to Roosevelt. Roosevelt agrees to establish a government committee with responsibility to look into whether fission is a military question worth worrying about. Einstein is essentially uninvolved with future fission work.

• Late 1942: After a series of slow starts and disinterest, the American work on fission begins in earnest, and the Manhattan Project — the project to actually build an atomic bomb, not just study whether they are feasible — begins.

I've obviously picked and chosen the events to include here, but it reflects my feeling on what sorts of things mattered or didn't. As you can see, Einstein and his work only shows up here and there. There is an entirely separate trajectory of investigation of particle physics that leads directly to the bomb. It was not begun by Einstein's work and Einstein's work played a very minor role in it. E=mc^2 is a convenient way to calculate energy release from fission (though not the only way at all, and not necessarily the most intuitive way), but it is not actually required for any of this. It does however provide a complement to work already going on regarding atomic structure, radioactivity, particle physics, and eventually fission.

Without getting too counter-historical, I think you can imagine a trajectory of science that develops an understanding of nuclear fission entirely without relativity. The fission process itself is non-relativistic. It is more intuitive to calculate the energy release primarily in terms of electrostatic repulsion of distended parts of a deformed nuclei. In terms of what actually happened, Einstein's work is not entirely alien to it — knowledge of his work was definitely in the heads of the people who worked on this stuff. However if Einstein had never existed and special relativity had never existed, it would not change the above timeline all too much, I don't think.

For people who are interested in what kinds of things physicists were thinking about in the exciting late-19th/early-20th century, Helge Kragh's Quantum Generations is an excellent (if sometimes perhaps too technical) history of physics, and is not teleological like many bomb-centric histories of physics are (e.g. Rhodes' book on the history of the atomic bomb, while excellent, of course is interested primarily in what led to the bomb — Kragh's book does include the bomb of course but is not oriented around it).

I've read that it may have been as much as a half-century before anyone else discovered the theory of relativity

That's only General Relativity. Special Relativity was actually a pretty obvious theory - all you needed to do was add an assumption that there's a velocity that's constant for all inertial frames. Someone else would've quickly figured it out if not Einstein.

Special Relativity is useful to compute energies and velocities of particles and gives rise to mass-energy equivalence which is also extremely useful for calculations in nuclear and particle physics.

So, yes, the theory of special relativity is very important to nuclear physics. But no, there's no strong indication that without Einstein this leap would've not been made during that time period.

It's speculated, however, that General Relativity was a huge leap given the existing state of physics and would've taken longer to derive without Einstein. But that's a very subjective and speculative statement and there's no evidence or science you can use to gauge these things - so you're unlikely to get a useful answer regarding that.

You might enjoy the following Wikipedia pages:

http://en.wikipedia.org/wiki/History_of_special_relativity

http://en.wikipedia.org/wiki/History_of_general_relativity

Edit: To definitively answer your question: No, the creation of atom bombs was not possible (unless by accident, somehow) without early quantum mechanics and special relativity.

No it would not be necessary. E = mc^2 applies to chemical reactions as well as nuclear reactions, but people were doing chemistry long before relativity.

Relativity allows us to understand the underlying mechanisms of nuclear weapons, but that understanding is largely academic with existing technology and would not be necessary to actually make the bomb.

Source: Am physical chemist.