We do not perceive time, of course. What we do perceive, albeit indirectly, is change: we see one situation, form a memory of it (or retain it in our short-term memory of what's happening), and then perceive another situation which differs from it. The notion of time is prompted by the notion of change; and the notion of a regular "flow" of time comes from a large array of cyclic changes — days, phases of the moon, seasons, planetary motions — which together suggest a steady rate at which things change.
If everything were to stop moving, time would have no significance that we know of. Time is only significant to us inasmuch as it is a framework for describing change. Indeed, philosophers of science such as Barbour have proposed that time is indeed an "illusion" which is suggested by change, or more precisely by a collection of distinct configurations of matter which we somehow perceive as (i) related to one another, as in being distinct states of a single system, and (ii) being ordered in time:
[Barbour's book] The End of Time advances timeless physics: the controversial view that time, as we perceive it, does not exist as anything other than an illusion [...] He argues that we have no evidence of the past other than our memory of it, and no evidence of the future other than our belief in it. "Change merely creates an illusion of time, with each individual moment existing in its own right, complete and whole." He calls these moments "Nows". It is all an illusion: there is no motion and no change. He argues that the illusion of time is what we interpret through what he calls "time capsules," which are "any fixed pattern that creates or encodes the appearance of motion, change or history."
Barbour's theory goes further in scepticism than the block universe theory, since it denies not only the passage of time, but the existence of an external dimension of time. Physics orders "Nows" by their inherent similarity to each other. That ordering is what we conventionally call a time ordering, but does not come about from "Nows" occurring at specific times, since they do not occur, nor does it come about from their existing unchangingly along the time-axis of a block universe, but it is rather derived from their actual content.
To distill this into a quick metaphor: you are meant to think of the universe not as a motion picture, nor even a static piece of film, but as a scattered and disorderly collection of frames from a film. They all exist simultaneously, and if we (as characters in the movie) perceive an ordering of time, this is because the similarity of adjacent frames induces an order on the frames.
However, does this mean that time is an illusion? While Barbour's ideas are treated with some seriousness, I find difficulty in understanding how an ordering obtained from similarity of co-existing "nows" differs from the block-universe picture of general relativity, which is essentially nothing more than the "nows" being explicitly ordered rather than implicitly; nor do I understand how the division of the world into "nows" comes about, nor why we should experience the echos of some "nows" as memories in other "nows". The simple reason is perhaps that some "nows" encode physical states of the brain which represent information about other "nows", and if one supposes that the universe is enormous and random, there will surely be systems which have such encodings — but why we should experience them is a mystery.
So Barbour has perhaps succeeded in reducing the notion of time to the hard problem of consciousness, provided a hypothesis about the universe being large and random enough to give rise to enough "nows" that there is a plausible sense of continuity. Even if we grant this: does this mean that time is an illusion? Provided that Barbour could explain why we experience anything if the universe consists of a static ensemble of "nows", this would rather be a mechanism (or rather construction) for the emergence of temporal change as an experience. Regardless of what underlies it, I am unable to avoid the simple fact that I experience change; therefore it does not really seem justifiable to dismiss time as a phenomenon (or a way of describing a phenomenon).
Time may not be a spatial dimension, and it may have subtle physical origins, but this does not mean that it does not 'exist'. One might as well say that matter is an illusion because our physical sensation of touch is based on electromagnetic fields propogating across small distances of "empty" space. The fact is that matter is not an illusion — our experiences are still described well by the notion of matter — it is simply that matter is not what our naïve impressions might suggest it is. The same may be true for time, and for time nevertheless to be 'real'.