Sure - it mostly means "over". It has loads of English cognates in that sense, e.g. överkomma = overcome, översikt = overview, etc.
ense is another word for being in agreement, so överens comes from that. I'm not sure why it was originally added, or even if that happened before the word reached Swedish.
I think it's from stemming. ense is an adjective, över makes it an adverb, komma makes it a verb, and -else makes it a noun. My guess as a student is över has stuck around to differentiate the words from ens komma: det var svårt att ens komma has a very different meaning from det var svårt att överenskomma. Thoughts?
It's hard to be absolutely certain, since it's a very old word and an even older loan. I can tell you the origins of ense, at least.
It originally comes from en, since being one would mean to share an opinion, or to strike an agreement. The -s suffix is a possessive, and as you say, the -e serves to make the possessive into an adjective and the -else makes a noun out of a verb.
But the över- appears to have first been a standalone word, and I can only trace it back to older versions of Low German. It's likely older than that, though, and I think in this case how the word was developed is reflected in its morphology rather than the other way around.