I asked internally about the upgrade as I have never performed the procedure myself. Technically it is possible to upgrade however you are going to have to upgrade in stages.
Before you can follow the guide on the website you need to get your Consul version to 0.8.5, there is a breaking change between 0.7 and 0.8 related to the raft protocol and this must be performed first.
Upgrading Specific Versions | Consul by HashiCorp
Then you will need to upgrade 0.8 to 1.2.4:
Upgrading to 1.2.4 | Consul by HashiCorp
Then 1.2.4 to 1.6.9:
Upgrading to 1.6.9 | Consul by HashiCorp
Then 1.6.9 to 1.9.1, the documentation below mentions the path to 1.8.4, but you should have no problems going straight to 1.9.1 as long as you make sure everything is running RAFT version 3.
Upgrading to 1.8.4 | Consul by HashiCorp
As an alternate approach, I would also consider a creating a parallel cluster which is running the latest version. This would require you to run two consul clusters and two agents (one 0.7 and one 1.9) on each machine but it would allow you to move each service over gradually. This approach would also enable you to slowly introduce service mesh features, service by service which would greatly reduce risk.
Sorry if this is quite a complicated process, but the version you are running was released over 4 years ago and is quite out of date. We try to keep the minor version upgrades as simple as possible but every now and then we need to change things like the RAFT format or the Gossip process. Version to version there is generally a smooth upgrade path but with such a big jump it would be very difficult for us to handle that.