I question your assumptions, however:
The idea of "parts" does not refer to things which are arbitrarily distinct within one whole. A rubber bouncy ball is not made of parts just because it takes up space - it is all part of the same whole, as opposed to a basketball consists of the sphere which bounces, the hollow inside which maintains its firmness, and the piece that allows the pump needle to insert air without letting air out. Hashem is One in that He does not have one "part" of Him responsible for kindness, one part for judgment, one part for mercy etc., rather Hashem is one in that all these behaviors are accomplished by one distinct "faculty." This is how the Ramchal describes Hashem's oneness in Derech Hashem (1:1:5) - מציאות פשוט בלי הרכבה - a simple existence, one that does not consist of compounding. This is the same use of simple that is commonly used in systems - simple and complex systems. Even if we could refer to Hashem as "being in all places" this would not result in "parts" of Him in different places, as all places would be one "big part."
Regarding your assumption that Hashem's unity means that He is in all places, Sha'ar HaYichud never states this and I do not think it is a result of his intent: there are two distinct aspects when we discuss the Creator. One is His עצם, His "essence," and the other is His מדות, His "attributes," the way He interacts with the world. Hashem's manifestation in this world, the way He interacts, is very much not singular in having no distinct parts - there are 13 distinct elements of that interaction. (The Kuzari explains that this itself is an expression of greater One-ness, that even apparent disparity comes from one unified source.) When we discuss Hashem being One, we are referring to His "essence" - there is no physical location to Hashem's "essence." All of His actions come from one cohesive plan and purpose, but the actions are split into parts, as is all of the physical world. Hashem does not have an "essence" in the physical world, and from the perspective of Hashem's "essence," physical existence does not exist (see Nefesh HaChaim Sha'ar Gimmel ch. 2 - עד שתוכל לומר שאין כאן שום נברא ועולם כלל רק הכל מלא עצמות אחדותו הפשוט). The discussion of His being one and having no parts is a discussion which precedes physical existence - thus the Rambam in several places (see for example Moreh 1:73) equates Hashem's one-ness with His being non-physical. There was never an attempt to apply the Unity that is being described to physical existence - it is a discussion of qualities and domains, not of how large or old something is.