Religion is a great cultural differentiator. People have been killing each other for many millenia, with a preference for targeting other people who belong to a distinct "culture", a rather loose term. From the outside, the god(s) people worship are quite easy to work out; if they are not the same as yours, then these people are "foreigners".
Historically, religion began to be a concept distinct from its host culture around 400 BC, at the time when true monotheism was invented. Before that period, there was no real difference, in the minds of people, between "your god is weaker than mine" and "your god does not exist"; early "monotheisms" such as Zoroastrianism and Mosaic Judaism were more properly defined as monolatrisms. The invention of the concept of monotheism came with the equally novel notion of your religion being something else than your ethnicity or culture; at that point, it became possible to die and kill for strictly religious reasons.
However, for persecutions to begin in earnest, it still required another ingredient: proselytism. In the Roman Empire, Jews were a troublesome component: conquest of Judea by Rome was not easy, and plagued by regular rebellions; but they were a people and their unrest was more political than religious. They did not try to expand their religion to other inhabitants of the Empire (especially after the destruction of the Temple in 70 AD: Judaism then restructured itself around the concept of orthodoxy, which de facto excluded the previously active non-mainstream branches which did try a bit of proselytism).
When Christianism appeared, it added the new component of proselytism, not only among Jews but also for all other humans (seemingly impulsed by the newly converted Paul of Tarse, against the advice of James the Just). Due to the exclusive nature of Christian worship, this lead to tensions with the Roman power, then persecution; and since the Christians were not defined by anything else than their religion (they were otherwise indistinguishable Roman citizens or slaves), the persecution was, necessarily, of a religious nature. Compounding the effect was the promise of an afterlife, with bonus granted in case of death when bearing witness of the new religion: that's what is called martyrdom. There is no martyr for Apollo or Jupiter, because when you die in the name of such deities, well, you still die, and you get no specific after-death benefit for it. With Jesus, martyrdom scores a VIP seat.
To sum up, you may get religious persecutions when all of the following hold:
- The concept of religion distinct from culture and ethnicity has emerged.
- A proselyte religion is active, leading to followers who are not distinguishable in a cultural way from the non-followers.
- Dying in the name of the religion grants benefits which make it worth.
In the Mediterranean area, these elements were all present with the advent of Christianism. You also find them in the case of Buddhism at the time of the Great Anti-Buddhist Persecution (9th century AD in China).
In earlier times, people already felt strongly about religion; but no situation arose where the religion alone could possibly serve as justification for mass killing. For instance, during the Third Punic War, the alleged practice of human sacrifices by Carthaginian was a recurrent theme of Roman propaganda, and Romans found it abhorrent. However, since Carthage was a distinct polity from Rome, its destruction is not described as religious persecution, even though the cessation of the practice of human sacrifice was one of the goals of the endeavour. (Whether the practice was real in the first place is an orthogonal issue.)
From a conceptual point of view, people tend to define themselves relatively to some absolute notions which can be religion, ethnicity, social class... and will fight each other based on their respective stance with regards to these notions. Your feeling that people "did not fell strongly about religion" prior to Christian times may be an illusion due to the fact that religion had not previously achieved, by itself, the status of a war-fuelling absolute.