Over-complicated is adding too many features, too much mechanism, too many moving parts. Over-engineering is far exceeding the requirements in an unhelpful way. For example: build me a treehouse. Said treehouse could probably be made of wood. If you made it out of concrete and steel, it might be a heck of a lot stronger and last a heck of a lot longer, without being more complicated (just more expensive). Too strong is over-engineered. If you made a treehouse with 13 bedrooms and an elevator, glass windows, solar power, and running water, that's overcomplicated.