While I don't know the first software to be referred to as an engine, it seemed useful to check Google's Ngram Viewer: 
As can be seen, database engine slowly began being to be used around 1979, while game engine took another decade to begin catching on. Checking a few books using software engine, they were using the phrase generally, in titles like Best Practices in Software Measurement and Practical Biometrics: From Aspiration to Implementation.
Darn, I left out graphics engine. Regraphing, I see it began around 1982 and in in 2008 shows about three times the usage of software engine, but still well below game engine.
I checked links and found results for:
- 1982: A 6809 based graphics engine used in Electrical Design News
- 1983: The inference engine is an interpreter of the facts and the rules. used in The Journal of Forth Application and Research - Volume 1
- 1987: Relational Database Engine used in Computer Architecture, Tutorial
- 1995: Wolfenstein 3-D game engine used in Game Developer magazine
(Be careful if you want most recent results with the Ngram Viewer. By default, it cuts off at 2000, which in this case misses the recent drop-off in usage.)
Stephen Kitt pointed out that inference engine peaks higher than everything else, and he is right. So I'm adding a 2nd graph with both that term and graphics engine. The phrase software engine was so minor I took it out.
"Everybody" was using inference engine in 1990, but the drop off from that year is dramatic. It must not have been cool any more.