Air carrier Captain reported crossing traffic failed to yield as cleared resulted in a conflict that required taking evasive action.

Narrative

We were at taxiway B short of K at EWR. We had received a taxi clearance from Newark ground control to pass behind Aircraft Y on S then taxi to 22R at W via K and R. We passed behind Aircraft Y and I made the verbal call clear left and the First Officer made the call clear right for taxiway S. As we approached taxiway Romeo I made the call clear left and as I looked to the right I noticed a very close and fast approaching Aircraft Z on the right. Our taxi light was on but I immediately stopped our aircraft and set the parking brake and turned off our taxi light. I knew the other aircraft was not slowing. The aircraft in question was apparently already on the tower frequency and went right in front of us and entered the 22R runway at B1. Had I not seen this aircraft on the right at the last second we would most likely have had a collision. I contacted Newark ground control and asked about the instructions for Aircraft Z. He stated that they were supposed to give way to us. I informed him that this did not happen. He then said ok and told us to continue our taxi to R then to Runway 22R at W and to monitor the tower. We complied and took off with no further incident.