This is not yet a full answer therefore I make it community wiki. I just want to share my ideas. Perhaps it's helpful.
As you know, both German and English are West Germanic languages. French, however, is a Romance language. So, you're presumably wondering why languages with different roots share a meaning. Well, to make it worse I guess Russian, a Slavic language, does have the same idiom, too.
My knowledge of Russian is too little so I can only come up with an example for "mit etw. rechnen". Perhaps someone can help me with an "auf etw. zählen" example. (@RegDwight?)
Я рассчитываю что ты сего́дня ве́чером придёт. (Ich rechne damit, dass du heute Abend kommst.)
I said, those languages don't share the roots. But going far, far back in history, all languages share the same root, though.
Of the twenty languages with the largest numbers of native speakers according to SIL Ethnologue, twelve are Indo-European: Spanish, English, Hindi, Portuguese, Bengali, Russian, German, Marathi, French, Italian, Punjabi, and Urdu, accounting for over 1.7 billion native speakers. Wiki
I highlighted the languages I mentioned before.
Since it's unlikely that all languages made the same development in recent times we can assume that this idiom is very old.
My guess is - but didn't found any sources - that the origin is the bible.
I tried to find some interesting hints in dictionaries about origin but nothing helpful here.
As a summary, here's what I collected:
Middle English (as a noun): from Old French counte (noun), counter (verb), from the verb computare 'calculate' (see compute) Oxford Dictionaries
Origin of COUNT
Middle English, from Anglo-French cunter, counter, from Latin computare, from com- + putare to consider Merriam Webster
First Known Use: 14th century
1642 T. Fuller Holy State iii. xxiii. 218 There is lesse honesty, wisdome, and money in men then is counted on. OED - cited in chat
zählen Vb. ‘eine Anzahl feststellen, gelten, mit jmdm. rechnen, sich auf jmdn. verlassen’, ahd. zellen (8. Jh.), mhd. zel(e)n, zellen DWDS
Balzac, noch immer auf den Tod und die Millionen des Herrn von Hanski zählend, lügt tapfer weiter — St. Zweig Balzac 342
besonders häufig in neuerer sprache auf einen oder etwas zählen, einen oder etwas bei rechnung, bestimmung, voraussicht eines künftigen sicher veranschlagen, im wechsel mit auf einen oder etwas rechnen Grimmsche Wörterbuch
vgl. th. 8, sp. 354: zählst du so gewisz auf deinen genius? Klinger 5, 312; auf dich ist gezählt Göthe 12, 66 Weim.; das hab ich euch nie gesagt, dasz ich unter der hiesigen garnison meine vögel habe, auf die ich zählen kann, wie auf meine höllenfahrt
Other sources like Wiktionary, The American Heritage Dictionary, or MacMillan Dictionary do not add any essential content.
My knowledge of Russian and French is too little to read monolingual dictionaries of those languages to get more information about its origin.
This is all I get yet. Hope it helps though.