This is The Fall of Chronopolis by Barrington J. Bayley.
The competing empires are the Chronostatic Empire and the Hegemony. The description of the temporal sea and the waves is in chapter two:
Time is composed of a wave structure. The nodes of the wave travel at intervals of approximately one hundred and seventy years and are of great interest to the time-traveller since they comprise “rest points” in the tensioning of the Chronotic energy field. This is of crucial importance in the business of time-travel, because matter can be transported from one node to another and will remain in place without any further expenditure of energy. On the other hand if matter is transported to a time between nodes, or conversely is taken from between nodes and is deposited somewhere else, it will not persist in its new location without a continuous expenditure of energy, usually accomplished by means of a device called an orthophase. This is the reason why nearly all Chronotic intercourse takes place from node to node. The seven nodes covered by the span of the empire form, as it were, the seven continents or provinces of the empire, while the intervening periods comprise a series of hinterlands, benevolently governed but rarely seeing a time-ship except in time of rebellion or by order of the Historical Office.
The cryptic computer is the Imperator:
For though the Imperator was a machine – admittedly much more advanced and mysterious than a common computer – it was also, in some indefinable way, alive.
More than that, it was in principle the true titular head of the empire. Emperor Philipium I – like any emperor before or after him – held his position by proxy, as it were. The rationale behind this system was quite clear: the Imperator contained the distillation of the minds of all the Chronotic emperors, of whom there had been five before Philipium, as well as of many other members of the imperial dynasty whose wisdom seemed to merit it, this distillation being accomplished by a transfusion from the memory centres of their brains after death.
Not that the Imperator was merely a receptacle of their dead intelligences; it was much more. No one quite knew what went on inside the Imperator, or what it did with these borrowed personalities. They never emerged, that was certain; the Imperator had a nature of its own.
...
The Imperator undertook no executive function. While it was consulted occasionally, the cryptic nature of its pronouncements rendered it more in the style of an oracle.
The sea you refer to is called the Strat and the beast that lurks within it is called Hulmu:
From that instant the universe of actuality was in danger. And that danger manifested almost immediately. During the early experiments there was an unfortunate accident whereby one of the assistants fell headlong into the temporal substratum. This man was Absol Humbart, later the Minion. He was caught by Hulmu, who realised that the weakening of orthogonal time offered him an opportunity to claw his way up and become real. But still it was not easy. In order to gain a foothold Hulmu needed first to acquire sufficient reality, in order to transfer himself to the surface.
For this Absol Humbart promised souls! If Hulmu could devour enough souls that had lived in orthogonal time, then he could erupt into our world and establish himself there, satisfying his enormous hunger to become real!
