Definition
let me highlight what I believe to be the critical part of data provenance that is not found in the definition of in data lineage:
providing a historical record of the data and its origins
Though the wording is different, I believe this addition is the only relevant difference in how provenance and lineage are defined.
Interpretation
The interpretation that I follow, and that I have seen used often in a Big Data context, is that lineage shows you which path the data has taken, but provenance allows you to know what the data looked like along the way.
Example
If you have a workflow that does this:
Gather input from source a, b > combine to c > update in 'random' fashion and store in d
Then I would say lineage allows you to know that the data went from a, b through c into d. Deep lineage would even allow you to see the logic used for this. However, this may not let you know what c looked like, in the theoretical random example this is hopefully clear, but in practice there are less random situations, but many irreproducible situations to the point where it might as well have been random.
Now provenance would keep track of the path taken, and on top of this also what the data looked like in c.
Note on implementation
As others mentioned, tracking and storing provenance can be a heavy burden, but it can be great to assist in development, especially of streaming data flows (it is like having a debug point everywhere). Furthermore there may be cases where the provenance is so important (or the data volume and number of transformations comparatively low) that one may want to keep the provenance for a certain period of time.
In practice provenance is not kept as long as lineage, but some tools like NiFi do capture it out of the box, keep it for a short while where it is most valuable, and in parallel track the normal lineage.
Full disclosure and disclaimer:
Though I am an employee of Cloudera, a company much involved with Governance, Lineage and products like NiFi, the description above is based on my personal experience, and from talking to colleagues and customers about Lineage and Provenance.