It should require attunement, and at least be rare
The game's main instruments for balancing magic items are attunement and item rarity.
The DMG provides guidance on creating new magic items on pages 285ff, so it cannot hurt if you read that, which will give you advise how to estimate power levels and how to avoid creating overpowered items. It says about combining items:
You can also modify an item by fusing it with
properties from another item. For example, you could
combine the effects of a helm of comprehending
languages with those of a helm of telepathy into a
single helmet. This makes the item more powerful
(and probably increases its rarity), but it won't break
your game.
In your case, both items are uncommon, and both require attunement. This is different from the example, where both are uncommon, but only the helm of telepathy requires attunement. I think this is the most powerful aspect you gain from combining them: it allows you to cheat on attunement slots (apart from that you would not be able to use two different kinds of magical footwear at the same time). Attunement is there for a reason: to avoid players stacking too many powers and effects and slowing down gameplay.
Combining the uncommon helms, only one of which needs attunement, already results in something that "probably should increase rarity". In your case, the item for sure should increase rarity, at least to rare, and of course, it should need attunement, too.
Rarity
A rare item typically (based on the guidance in the DMG for handing out magical items and based on the treasure tables for encounters) would mean that you would get access to it later on. Xanathar's Guide to Everything has a table that shows the expected distribution on page 135. Both kinds of boots are classified as "major items", and you could expect to obtain two such uncommon items in tier 1 (level 1-4). However, you should not expect a rare major item before tier 2 (level 5-10), and not find more than one there.
Your DM can of course ignore such guidance, and if they do, they should think about how to reward other players to keep things fair. Otherwise, you may have to wait for this item until you are higher level, which may not be what you are trying to achieve.
Attunement
The DMG provides this guidance:
If having all the characters in a party pass an item
around to gain its lasting benefits would be disruptive,
the item should require attunement.
Your new boots, as the two original kinds, can be passed around easily. Want everyone to climb up a castle wall? Walk up, throw down your super-boots, have the next character walk up. So, it should require attunement, like the base items.
To give you this effect without attunement would be an item that in a way gave you two free attunement slots. That is extremely powerful, and you should be careful with it. Further increasing rarity to a very rare or legendary major item would also mean you should not expect this before tier 3 (level 11-16), when most campaigns are already winding down. Like the DMG, I recommend you do not make this free of attunement.
P.S. The chapter on creating magic items is rather short, and, to be honest, the designers themselves did a pretty shoddy job in assigning rarity to their items. For example a broom of flying is an uncommon item that allows you to fly for however long you like, while the wings of flying are a rare item that allow you to fly for just 1 hour (and only a little faster), before needing to recharge for 1d12 hours. So, the really best answer is to test your new item in game, and be open minded about taking it down a notch if it turns out to be too strong, or up, if too weak.
