tl;dr
Use the -LiteralPath parameter to pass a path meant to be interpreted literally (verbatim) to the Set-Location cmdlet, which cd is a built-in alias of; by default (via the positionally implied -Path parameter), it is interpreted as a wildcard expression:
# * "cd" is a built-in alias of "Set-Location"
# * "sl" is the preferable, PowerShell-idiomatic built-in alias
# * Interactively, using PowerShell's elastic syntax,
# you can shorten "-LiteralPath" to "-l", given that no other parameter name
# (currently) starts with "l"
# * In PowerShell (Core) 7+, "-lp" is an official alias.
cd -LiteralPath $tmp_dir
The same applies analogously to rm (unlike what your question implies), which is a built-in alias of Remove-Item.
By contrast, mkdir (which is a wrapper function for New-Item -ItemType Directory) implicitly treats its argument literally.
Read on for details.
As for what you tried:
While cd and mkdir look like their cmd.exe counterparts, they are not:
cd is a built-in alias of the Set-Location cmdlet.
mkdir is a built-in wrapper function for the New-Item cmdlet, with implicitly applied argument -ItemType Directory.
(On Unix-like platforms, mkdir isn't an alias at all and instead refers to the external /bin/mkdir utility).
To learn what command a given name (ultimately) refers to in PowerShell, use the Get-Command cmdlet; e.g. Get-Command cd)
Thus,
cd $tmp_dir
is equivalent to the following call, given that Set-Location binds a positional argument (one not preceded by the target parameter name) to its -Path parameter:
Set-Location -Path $tmp_dir
Most PowerShell cmdlets interpret -Path arguments as wildcard expressions, including - perhaps surprisingly - Set-Location.[1]
Typically, the distinction between -Path and -LiteralPath doesn't matter, given that * and ? - the usual wildcard characters - aren't even allowed in file and directory names (at least on Windows).
However, the problem is that in PowerShell's wildcard language [ and ] also have special meaning (they form character sets - e.g. [abc] and/or character ranges - e.g. [a-c]), which conflicts with literal use of [ and ] in file names, and necessitates the use of -LiteralPath for disambiguation.[2]
By contrast, New-Item's (possibly positionally implied) -Path parameter acts like -LiteralPath, because interpreting a path argument as a wildcard expression in the context of creating a file or directory is pointless. That's why you had no problem creating a directory whose path literally contains [ and ] with mkdir.[3]
Why aliases named for a different shell's commands - such as cd and mkdir - are best avoided in PowerShell:
In a problematic attempt to ease the migration pain for cmd.exe users (and in part also for users of POSIX-compatible shells), PowerShell decided to define built-in aliases and wrapper functions that are named for cmd.exe's internal commands, whereas PowerShell's analogous internal commands, the so-called cmdlets, have very different names.
The latter isn't problematic per se - except that by their use you're missing out on the benefits of PowerShell's standard verb-noun naming convention (e.g., Set-Location), which also extends to how aliases are formed, given that the approved verbs have official alias forms (e.g., s for Set-; therefore, sl is another, but PowerShell-idiomatic Set-Location alias).
What is problematic, however, is that PowerShell commands have very different syntax from cmd.exe's.
If you use names such as cd and mkdir, you'll be tempted to think that, e.g. cd and mkdir function the same way as in cmd.exe - which is only true in the most basic of use cases, however.
It's best to use the true PowerShell command names or - for brevity in interactive use - their PowerShell aliases, which are (reasonably) predictably formed, as discussed above (e.g., sl for Set-Location and ni for New-Item)
[1] By contrast, cmd.exe's cd command does not accept wildcards. With Set-Location, wildcard support is of conceptual necessity limited, because the wildcard expression must resolve to exactly one matching directory.
[2] Alternatively, with -Path you can escape [ and ] as `[ and `], respectively, but this kind of escaping doesn't work consistently as of PowerShell 7.3.0 - see GitHub issue #7999.
[3] This parameter-naming inconsistency is unfortunate; arguably, -LiteralPath should at least be supported as a parameter alias name for -Path. That said, as of PowerShell 7.3.0, there is actually a case where -Path currently is interpreted as a wildcard expression, namely when combined with the -Name parameter, but this should be considered a bug - see GitHub issue #17106.